E. Ирмэг бүрийн хувьд хамгийн бага спэннинг мод

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

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

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

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

Холбогдсон чиглэлгүй жинтэй граф өгөгдсөн ба өөртэйгээ холбогдсон оройгүй ба давхар ирмэггүй граф байна. Графд $n$ орой бай $m$ ирмэг агуулагдана.

$(u, v)$ ирмэг бүрийн хувьд $(u, v)$ ирмэгийг агуулсан боломжит хамгийн бага жинтэй спэннинг модийг (энэ нь графийн бүх оройг агуулсан боловч зарим орой хоорондоо ирмэгээр холбогдоогүй байж болно) ол.

Спэннинг модны жин нь түүний агуулж байгаа бүх ирмэгүүдийн жингийн нийлбэр байна.

Оролт

Эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $m$ ($1 ≤ n ≤ 2*10^{5}, n - 1 ≤ m ≤ 2*10^{5}$) байх ба графын оройнууд болон ирмэгүүдийн тоо байна.

Дараагийн $m$ мөр бүрт гурван бүхэл тоон утга $u_{i}, v_{i}, w_{i}$ ($1 ≤ u_{i}, v_{i} ≤ n, u_{i} ≠ v_{i}, 1 ≤ w_{i} ≤ 10^{9}$) байх ба $i$-р ирмэгийн төгсгөлийн цэгүүд болон ирмэгийн жин байна.

Гаралт

$m$ мөр хэвлэнэ. $i$-р мөрөнд $i$-р ирмэгийг агуулсан спэннинг модны боломжит хамгийн бага жин байх ёстой.

Ирмэгүүд оролтонд өгсөн дарааллаараа $1$-c $n$ хүртэл дугаарлагдсан.

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

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

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