Пашмакийн даалгавар нь графийн бодлого байв. Хэдийгээр тэр чадахаараа оролдсон ч бодож чадахгүй л байна. Таны мэдэж байгаачлан тэр графийн онолд үнэхээр тааруу юм, тэгэхээр түүнд бодлогоо бодоход нь тусална уу.

$n$ оройтой $m$ ирмэгтэй жинтэй чиглэлтэй граф ѳгѳгдсѳн. Замын турш таарах ирмэгүүдийн жин ѳсдѳг байх хамгийн их ирмэгтэй замыг олох шаардлагатай. Ѳѳрѳѳр хэлбэл уг замын ирмэг бүр ѳмнѳх ирмэгээсээ илүү жинтэй байна.

Пашмакд тусалж, шаардлагатай замын ирмэгүүдийн тоог хэвлэнэ үү.

Оролт

Эхний мѳрѳнд $n$, $m$ $(2 ≤ n ≤ 3*10^{5}; 1 ≤ m ≤ min(n*(n - 1), 3*10^{5}))$ бүхэл тоо байрлана. Тэгээд дараа нь $m$ мѳр байрлана. $i$-р мѳр нь зайгаар тусгаарлагдсан $u_{i}$, $v_{i}$, $w_{i}$ $(1 ≤ u_{i}, v_{i} ≤ n; 1 ≤ w_{i} ≤ 10^{5})$ бүхэл тоонуудыг агуулна. Энэ нь $u_{i}$, $v_{i}$ оройнууд $w_{i}$ жинтэй ирмэгээр холбогдсоныг илтгэнэ.

Уг графд гогцоо болон давхар ирмэг байхгүй.

Гаралт

Бодлогын хариу болох ганц тоог хэвлэ.

Нэгдүгээр жишээний хувьд дараах замуудын аль нь ч байж болно: .

Хоёрдугаар жишээний хувьд хамгийн их ирмэгтэй зам нь .

Гуравдугаар жишээний хувьд хамгийн их ирмэгтэй зам нь .