mesaj3

Mesaj 3

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

h2. Restrictii
* $2 < N < 11011$

* $2 < M < 110011$

* $0 < M < 110011$

* $0 < X{~i~} < 1111$, pentru orice $1 &le; i &le; M$
* $1 &le; a{~i~}, b{~i~} &le; N$, pentru orice $1 &le; i &le; M$
* Nu vor exista mai mult de $9$ mesageri care sa treaca prin acelasi oras.

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

1899