E. Малчны этгээд зан

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

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

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

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

Бовиниагийн газарт $n$ бэлчээр бий боловч бэлчээрүүдийг холбосон замууд байхгүй. Мэдээж энэ бол аймшигтай нөхцөл байдал бөгөөд Кевин Сан ялгаатай хос бэлчээрийг холбох чиглэлгүй $m$ зам барьж засварлахаар төлөвлөж байгаа. Тээвэрлэлтийг илүү үр дүнтэй болгохын тулд тэр эдгээр замуудын заримд нь хучилт хийхээр төлөвлөсөн.

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

Оролт

Эхний мөрөнд хоёр бүхэл тоон утга $n$ ($2 ≤ n ≤ 100 000$) ба $m$ ($1 ≤ m ≤ 300 000$) байх ба харгалзан бэлчээрүүд болон замуудын тоо байна. Дараагийн $m$ мөр бүрт гурван бүхэл тоон утга $a_{i}$, $b_{i}$ ба $l_{i}$ байх ба $i$-р замыг тодорхойлно. $i$-р зам нь $a_{i}$ ба $b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$; $a_{i} ≠ b_{i}$) бэлчирүүдийг холбох ба $l_{i}$ ($1 ≤ l_{i} ≤ 10^{9}$) урттай байна. Замууд байгуулагдсан дарааллаараа өгөгдөнө.

Гаралт

$m$ мөр хэвлэнэ. $i$-р мөрөнд нэг бүхэл тоон утга байх ба зөвхөн эхний $i$ замыг ашигласан нарлаг хучилт дахь хамгийн урт замын (хамгийн их ачаалалтай ирмэг) боломжит хамгийн бага урт байна. Хэрвээ Кевин бэлчир бүр сондгой тооны хучилттай замтай холбоотой байх замуудын бүрдлийг хучиж чадахгүй бол $ - 1$-г хэвлэ.

Хучилт хийх нь зөвхөн таамгийн буюу таны $i$-р замыг нэмсэний дараах хариултад өмнөх хариултуудын аль нь ч нөлөөлөх ёсгүй.

Орчуулсан: Г.Мэндбаяр

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

Оролт
4 4
1 3 4
2 4 8
1 2 2
3 4 3
Гаралт
-1
8
8
3
Оролт
3 2
1 2 3
2 3 4
Гаралт
-1
-1
Оролт
4 10
2 1 987
3 2 829
4 1 768
4 2 608
3 4 593
3 2 488
4 2 334
2 1 204
1 3 114
1 4 39
Гаралт
-1
-1
829
829
768
768
768
488
334
204

Тэмдэглэл

Эхний жишээний хувьд Кевин $i$-р замыг барьсаны дараах замууд:

  1. Замуудын ямар ч бүрдэл ажиллахгүй.
  2. 1 ($4$ урттай) болон 2 ($8$ урттай) замууд.
  3. 1 ($4$ урттай) болон 2 ($8$ урттай) замууд.
  4. 3 ($2$ урттай) болон 4 ($3$ урттай) замууд

Хоёр дахь жишээн дээр Кевинийг баяртай байлгах хучилт оршин байхгүй.

Сэтгэгдлүүдийг ачааллаж байна...