Ezis Toretto™ un viņa bruņurupuču-jājošā ģimene vēlas aplaupīt skudrulāču kontrolēto pārvedumu ar kukaiņiem. Pārvedums notiek jau pēc 3 stundām un šāda iespēja vairs nebūs līdz nākamajam pilnmēnesim. Ir jārīkojas tagad!

Ir tikai viena problēma: viņš nezina ne pārveduma sākuma atrašanās vietu, ne tā maršutu. Toties ir zināms, ka skudrulāči atgriezīsies sākuma pozīcijā un vienu un to pašu ceļu neizmantos divas reizes.

Kā Eža Toretto™ ģimenei sadalīties pa pilsētu, lai vismaz viena grupa sastaptos ar skudrulāču pārvedumu?

Pirmajā rindā dots pilsētas krustojumu škaits n un ceļu skaits m. Katrs celš savieno 2 krustojumus. (3 ≤ n ≤ m ≤ 10⁵).

Tālāk seko m rindas, katra saturot 3 skaitļus a, b, c – krustojumi a un b, kurus savieno ceļš, un uz ceļa novietojamo ežu skaits c, kas vajadzīgs, lai garantēti aplaupītu pārvedumu (0 < a, b ≤ n, a ≠ b, 0 < c < 100).

Neviens ceļš ievaddatos neatkārtosies un visi ceļi ir divvirziena.

Vienīgajā rindā jaizvada minimālais ežu skaits, kas vajadzīgs, lai garantētu pārveduma aplaupīšanu. 

Parauga testā tiek novietoti 2 eži uz ceļa 1-2 un 3 eži uz ceļa 3-5.