Холбогдсон чиглэлгүй жинтэй граф өгөгдсөн ба өөртэйгээ холбогдсон оройгүй ба давхар ирмэггүй граф байна. Графд $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$ хүртэл дугаарлагдсан.