Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
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