C. Хагарал

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Дахиад л Берландад маш хүнд цаг үе иржээ! Маш олон хотууд хоорондоо бүр иргэний дайн хүртэл зарлах хүйтэн харилцаатай болсон байв.

Берландад $n$ ширхэг хотууд байх бөгөөд эдгээрийн зарим нь 2 урсгалтай замуудаар холбогдсон байв. Түүнчлэн ямар нэгэн хотоос бусад аль ч хот уруу эдгээр замуудыг ашиглан хүрч болно гэдэг нь баталгаагүй байв. Өөрөөр хэлбэл заавал хүрч болдог байх албагүй.

$s$ болон $t$ хотууд нь өөрсдийн харилцаагаа эцэс болсноо зарласан бөгөөд одоо эдгээр хотуудын хооронд өгөгдсөн замуудыг ашиглан явах боломжийг хязгаарлахыг хүсэж байв. Одоо магадгүй хэд хэдэн замыг хаах хэрэгтэй бөгөөд ингэснээр өгөгдсөн замуудыг ашиглан $s$-ээс $t$ хот уруу хүрэх нь боломжгүй болох ёстой юм. Хот болгон нь нэгээс олонгүй замыг хаахад зориулан мөнгө төлөхийг зөвшөөрсөн бөгөөд түүнчлэн нийт хаагдсан замуудын тоо нь 2-оос ихгүй байх ёстой ажээ.

Тэгвэл эдгээр хотуудад туслан эдгээр замуудыг хаасны дараа $s$ болон $t$ хотуудын хооронд явах боломжгүй байх 2-оос олонгүй замуудын олонлогийг олж өгнө үү. Зам бүрийн хувьд уг замыг хаах зардлын хэмжээ нь тооцоологдсон байна. Тэгвэл боломжит бүх хаах ёстой замуудын олонлогоос нийт зардлын хэмжээ нь хамгийн бага байх замуудын олонлогийг олно уу.

Оролт

Оролтын эхний мөрөнд 2 бүхэл тоо $n$ болон $m$ ($2 ≤ n ≤ 1000$, $0 ≤ m ≤ 30 000$) өгөгдөх ба эдгээр нь Берландад байх хотуудын тоо болон замуудын тоог тус тус илэрхийлнэ.

2-дахь мөрөнд бүхэл тоонууд $s$ болон $t$ ($1 ≤ s, t ≤ n$, $s ≠ t$)-ууд өгөгдөх ба эдгээр нь харилцаагаа тасалж буй хотуудын дугааруудыг илэрхийлнэ.

Дараа нь $m$ ширхэг мөр өгөгдөх ба мөр болгонд 3 ширхэг бүхэл тоо $x_{i}$, $y_{i}$ болон $w_{i}$ ($1 ≤ x_{i}, y_{i} ≤ n$, $1 ≤ w_{i} ≤ 10^{9}$) өгөгдөх бөгөөд эдгээр нь $i$-дахь замаар холбогдож буй хотуудын дугаарууд болон уг замыг хаахад шаардагдах зардлын хэмжээг тус тус илэрхийлнэ.

Бүх замууд нь 2 урсгалтай байна. Мөн ямар нэгэн хос хотууд нь хоорондоо нэгээс олон тооны замаар холбогдсон байх боломжтой юм. Түүнчлэн аливаа хотыг өөртэй нь холбосон зам байж болохыг анхаарна уу.

Гаралт

Гаралтын эхний мөрөнд хэрэв $s$ болон $t$-р хотуудын харилцааг таслахын тулд 2-оос ихгүй зам хаах шаардлагатай бол харилцааг таслахад шаардагдах хамгийн бага зардлын хэмжээг хэвлэнэ үү.

2-дахь мөрөнд бодлогын оновчтой хариултын явцад хаах ёстой замын тоог илэрхийлэх $c$ ($0 ≤ c ≤ 2$) тоог хэвлэнэ.

3-дахь мөрөнд $1$-ээс $m$ хүртэлх ялгаатай $c$ ширхэг бүхэл тоонуудыг дурын дарааллаар хэвлэх бөгөөд энэ нь хаагдах ёстой замуудын дугааруудыг илэрхийлэх юм. Замуудыг оролтод өгөгдсөн дарааллаараа $1$-ээс $m$ хүртэл дугаарлагдсан гэж үзнэ үү.

Хэрэв $s$ болон $t$-р хотуудын харилцааг 2-оос ихгүй зам хааснаар таслах боломжгүй байвал гаралтад -1 гэж бичсэн ганц мөр хэвлэхэд болно.

Хэрэв хэд хэдэн боломжит хариултууд байвал та тэдгээрийн алийг нь ч хэвлэсэн болно.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
6 7
1 6
2 1 6
2 3 5
3 4 9
4 6 4
4 6 5
4 5 1
3 1 3
Гаралт
8
2
2 7
Оролт
6 7
1 6
2 3 1
1 2 2
1 3 3
4 5 4
3 6 5
4 6 6
1 5 7
Гаралт
9
2
4 5
Оролт
5 4
1 5
2 1 3
3 2 1
3 4 4
4 5 2
Гаралт
1
1
2
Оролт
2 3
1 2
1 2 734458840
1 2 817380027
1 2 304764803
Гаралт
-1
Сэтгэгдлүүдийг ачааллаж байна...