h2. Date de intrare

Fisierul de intrare $mesaj3.in$ contine pe prima linie numarul natural $N$, reprezentand numarul de orase din Bucovina. Urmatoarele $N - 1$ linii contin cate doua numere naturale distincte separate printr-un spatiu $a b$ cu semnificatia "exista o sosea care conecteaza direct orasele $a$ si $b$". Pe linia $N + 1$ este scris un numar natural $M$ reprezentand numarul de mesageri. Pe urmatoarele $M$ linii se afla informatii despre cei $M$ mesageri. Pe cea de a $i$-a linie dintre cele $M$ $(1 ≤ i ≤ M)$ sunt scrise trei numere naturale separate prin cate un spatiu $a{~i~} b{~i~} X{~i~}$, cu semnificatia "mesagerul $i$ parcurge ruta de la orasul $a{~i~}$ la orasul $b{~j~}$, fiind platit cu $X{~i~}$ galbeni".

Fisierul de intrare $mesaj3.in$ contine pe prima linie numarul natural $N$, reprezentand numarul de orase din Bucovina. Urmatoarele $N - 1$ linii contin cate doua numere naturale distincte separate printr-un spatiu $a b$ cu semnificatia "exista o sosea care conecteaza direct orasele $a$ si $b$". Pe linia $N + 1$ este scris un numar natural $M$ reprezentand numarul de mesageri. Pe urmatoarele $M$ linii se afla informatii despre cei $M$ mesageri. Pe cea de a $i$-a linie dintre cele $M$ $(1 ≤ i ≤ M)$ sunt scrise trei numere naturale separate prin cate un spatiu $a{~i~} b{~i~} X{~i~}$, cu semnificatia "mesagerul $i$ parcurge ruta de la orasul $a{~i~}$ la orasul $b{~i~}$, fiind platit cu $X{~i~}$ galbeni".

h2. Date de iesire

Exista si alte solutii, dar pentru acestea suma necesara este mai mare.
== include(page="template/taskfooter" task_id="mesaj3") ==

 
 
==SmfTopic(topic_id="1899")==

1899