== include(page="template/taskheader" task_id="transport2") ==

Poveste şi cerinţă...

Se cunoaşte că un autovehicul nu poate circula pe un drum decât dacă masa sa nu depăşeşte masa maximă autorizată a drumului. În calcularea masei autovehiculului se consideră şi pasagerii, mărfurile etc.
 
h3. Cerinţă
 
Astfel, se dă o hartă sub forma unui graf neorientat, unde nodurile numerotate de la $1$ la $n$ reprezintă localităţile, iar muchiile reprezintă drumurile, împreună cu o masă maximă autorizată. Determinaţi greutatea maximă a unui autovehicul care poate ajunge legal din sursă (nodul $1$) la destinaţie (nodul $n$).

h2. Date de intrare

Fişierul de intrare $transport2.in$ ...

Fişierul de intrare $transport2.in$ conţine pe prima linie două numere naturale $n$ şi $m$, reprezentând numărul nodurilor şi, respectiv, numărul muchiilor. Pe următoarele $m$ linii se află câte trei numere naturale $x$ $y$ $w$, separate prin câte un spaţiu, reprezentând o muchie de masă maximă autorizată $w$ între nodurile $x$ şi $y$.

h2. Date de ieşire

În fişierul de ieşire $transport2.out$ ...

În fişierul de ieşire $transport2.out$ veţi afişa o singură valoare, reprezentând greutatea maximă admisă a unui autovehicul care poate ajunge legal din nodul $1$ în nodul $n$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ n ≤ 200$
* $1 ≤ m ≤ n(n - 1)/2$
* $1 ≤ w ≤ 10 000$
* Ministrul transporturilor a decis că toate drumurile au masa maximă autorizată un număr întreg.
* Se garantează că există cel puţin un drum care leagă nodul $1$ de nodul $n$.

h2. Exemplu
table(example). |_. transport2.in |_. transport2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 6 9
1 2 5
1 4 3
2 4 2
2 3 6
4 5 4
3 4 5
3 5 1
3 6 3
5 6 5
| 4

|
h3. Explicaţie

...

Soluţia corespunde traseului $1$ - $2$ - $3$ - $4$ - $5$ - $6$ ce are costurile $5$, $6$, $5$, $4$ şi respectiv $5$. Orice alt traseu va avea o greutate maximă autorizată mai mică decât $4$.

== include(page="template/taskfooter" task_id="transport2") ==