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

Poveste şi cerinţă...

Aceasta este o problema medie.
 
Gigel are un autobuz si, fiindca este un bun cetatean vrea sa transporte persoane cu autobuzul sau. Cum drumurile nu au o infrastructura foarte buna,se impune o limita maxim admisa de pasageri.
 
h2. Cerinta
 
Se da o harta, codificata sub forma unui graf neorientat unde nodurile numerotate de la 1 la n reprezintă localităţile, iar muchiile reprezintă drumurile, impreuna cu numarul maxim de pasageri admisi. Determinaţi numarul maxim de pasageri pe care Gigel ii poate transporta, legal, plecand din orasul 1 pana in orasul N.

h2. Date de intrare

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

Fişierul de intrare autobuz.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 p, separate prin câte un spaţiu, cu urmatoare semnificatie, pe drumul de la orasul x la orasul y se pot transporta maxim p pasageri.

h2. Date de ieşire

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

În fişierul de ieşire autobuz.out veţi afişa o singură valoare, reprezentând numarul maxim de pasageri pe care Gigel in poate transporta, legal, din orasul 1 în orasul N.

h2. Restricţii

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

* 2 ≤ N ≤ 100 000
* 1 ≤ M ≤ 200 000
* 1 ≤ p ≤ 10 000
* Se garanteaza ca exista un drum din orasul 1 in orasul N
* Gigel nu este pasager.

h2. Exemplu
table(example). |_. autobuz.in |_. autobuz.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

...

Gigel urmeaza urmatorul traseu: 1 -> 2 -> 3 -> 4 -> 5 -> 6 si poate transporta maxim 4 pasageri.

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