E. Пашмак ба граф

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

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

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

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

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

$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}$ жинтэй ирмэгээр холбогдсоныг илтгэнэ.

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

Гаралт

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

Орчуулсан: Sugardorj

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

Оролт
3 3
1 2 1
2 3 1
3 1 1
Гаралт
1
Оролт
3 3
1 2 1
2 3 2
3 1 3
Гаралт
3
Оролт
6 7
1 2 1
3 2 5
2 4 2
2 5 2
2 6 9
5 4 3
4 3 4
Гаралт
6

Тэмдэглэл

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

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

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

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