Admiral#4022
Mixael Adriaanszoon de Ruyter tarixdə ən məşhur Niderland admirallarından biri kimi tanınır və -ci əsrdəki İngilis-Hollandiya müharibələrində böyük şöhrət qazanmışdır. De Ruyter şəxsən bayraq gəmisinə rəhbərlik edirdi və dəniz döyüşləri zamanı müttəfiq hərbi gəmilərə əmrlər verirdi.
De Ruyter dövründə qraf nəzəriyyəsi yeni yaranmağa başlamışdı və admiral dəniz döyüşlərini planlaşdırarkən onun bütün üstünlüklərindən istifadə edirdi. Dənizdəki yol nöqtələri zirvələrlə göstərilir və onların arasındakı mümkün keçidlər istiqamətli kənarlarla təmsil olunur. Hər hansı iki yol nöqtəsi W_1 və W_2 üçün W_1 \rightarrow W_2 keçidi ən çox bir dəfə mövcuddur. Hər istiqamətli kənarda, müvafiq keçid boyunca gəmini təhlükəsiz şəkildə aparmaq üçün düşmən gəmilərini batırmaq məqsədilə atılmalı olan top nüvələrinin sayı qeyd olunur.
De Ruyterin ən uğurlu taktikalardan biri də De Ruyter manevri idi. İki hərbi gəmi bir nöqtədən çıxır, ayrılır və düşmən donanmasını yararaq təyinat nöqtəsində birləşirdi. Manevr iki gəminin müxtəlif marşrutlarla hərəkət etməsini nəzərdə tutur, bu marşrutlar nə yol nöqtələrində (başlanğıc və son nöqtə istisna olmaqla), nə də keçidlərdə döyüş zamanı kəsişmir.
Niderlandlı olaraq, admiral de Ruyter pul xərcləməyi sevmirdi; -ci əsr dəniz müharibəsində bu, mümkün qədər az bahalı top nüvəsi istifadə etmək demək idi.
De Ruyter taktikasının qraf şəklində vizuallaşdırılmış konkret nümunəsi. İki gəmi (\textit{qırmızı} və \textit{mavi}) ümumi başlanğıc nöqtəsindən () ümumi son nöqtəyə () hərəkət edir. Qırmızı gəminin yolu 1 \rightarrow 3 \rightarrow 6 (yolda nüvə atılmalıdır); mavi gəminin yolu 1 \rightarrow 2 \rightarrow 5 \rightarrow 4 \rightarrow 6 (yolda nüvə atılmalıdır). Manevr zamanı ümumilikdə nüvə atılmalıdır. Başlanğıc və son nöqtə istisna olmaqla, heç bir zirvə və heç bir kənar hər iki gəmi tərəfindən ziyarət edilmir.
Hər test aşağıdakılardan ibarətdir:
iki tam ədəd (3 \le v \le 1000) və (3 \le e \le 10000) - yol nöqtələrinin və keçidlərin sayı.
daha sonra hər keçid üçün üç tam ədəd olan sətir gəlir:
a_i (1 \le a_i \le v) - keçidin başlanğıc nöqtəsi;
b_i (1 \le b_i \le v, a_i \ne b_i) - keçidin son nöqtəsi. Bütün keçidlər istiqamətlidir;
c_i (1 \le c_i \le 100) - keçid boyunca hərəkət edərkən atılmalı olan top nüvələrinin sayı.
Hərəkətin başlanğıc nöqtəsi , son nöqtəsi -dir. Həmişə və nöqtələri arasında ən azı iki fərqli yol mövcuddur.
Hər test üçün hər iki gəminin manevr son nöqtəsinə çatması üçün istifadə olunmalı olan ən az ümumi nüvə sayını çıxış edin.
Nümunə 1