Nosaukums
Ātrs un bez ežastības (ff4)
Laika limits
0.50s
Atmiņas limits
64.0 MB
Grūtība
65%

Definīcija

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?

Ežu izvietojums parauga testā


Ievaddatu raksturojums

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

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.


Izvaddatu raksturojums

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


Piezīmes

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


Paraugdati

Stdin
6 7
1 2 2
2 4 6
1 6 3
2 5 5
4 3 4
6 5 4
5 3 3
Stdout
5

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.