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

A fost odata un camionas care se afla intr-un basm. In lumea basmului existau $N$ sate, numerotate de la 1 la $N$ si $M$ drumuri bidirectionale de legatura intre ele. Cum nici macar in basme drumurile nu sunt construite cum trebuie, fiecare din cele $M$ drumuri au o rezistenta $g ~i~$. Basmul nostru este insa un basm modern, iar **PIZZA** este unul dintre elementele de baza ale acestuia. Camionasul nostru are o greutate $G$ si se afla initial, in satul $1$. Acesta are misiunea de a transporta **PIZZA** din satul $1$, catre satul $N$. Fiind foarte de treaba, camionasul se gandeste ca nu ar fi indicat sa mearga pe drumuri care au rezistenta mai mica strict decat greutatea sa, pentru ca aceste drumuri s-ar strica. Totusi, cum livrarea de **PIZZA** este menirea sa pe lume, acesta se intreaba care este numarul minim de drumuri a caror rezistenta trebuie marita, astfel incat el sa poata transporta **PIZZA** din satul $1$ in satul $N$, fara sa fie nevoit sa mearga pe drumuri cu rezistenta strict mai mica decat greutatea sa.

A fost odata un camionas care se afla intr-un basm. In lumea basmului existau $N$ sate, numerotate de la 1 la $N$ si $M$ drumuri bidirectionale de legatura intre ele. Cum nici macar in basme drumurile nu sunt construite cum trebuie, fiecare din cele $M$ drumuri au o rezistenta $g{~i~}$. Basmul nostru este insa un basm modern, iar **PIZZA** este unul dintre elementele de baza ale acestuia. Camionasul nostru are o greutate $G$ si se afla initial, in satul $1$. Acesta are misiunea de a transporta **PIZZA** din satul $1$, catre satul $N$. Fiind foarte de treaba, camionasul se gandeste ca nu ar fi indicat sa mearga pe drumuri care au rezistenta mai mica strict decat greutatea sa, pentru ca aceste drumuri s-ar strica. Totusi, cum livrarea de **PIZZA** este menirea sa pe lume, acesta se intreaba care este numarul minim de drumuri a caror rezistenta trebuie marita, astfel incat el sa poata transporta **PIZZA** din satul $1$ in satul $N$, fara sa fie nevoit sa mearga pe drumuri cu rezistenta strict mai mica decat greutatea sa.

Cum camionasul nostru nu este tocmai un expert in teoria grafurilor, s-a gandit ca tocmai voi il puteti ajuta, furnizandu-i raspunsul la aceasta intrebare.

h2. Restricţii

* $1 ≤ N ≤ 100.000$
* $1 ≤ M ≤ 200.000$

* $1 ≤ N ≤ 50.000$
* $1 ≤ M ≤ 100.000$

* $1 ≤ G ≤ 1.000.000$

* $1 ≤ g ~i~ ≤ 1.000.000$
* **PIZZA** este elementul cheie in rezolvarea acestei probleme!

* $1 ≤ g{~i~} ≤ 1.000.000$
* $Se garanteaza ca exista cel putin un lant intre satul 1 si satul N.$
* $**PIZZA** este elementul cheie in rezolvarea acestei probleme!$

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

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

| 6 6 7
1 2 8
2 5 6
5 6 5
1 3 7
3 4 11
4 6 3
| 1

|

h3. Explicatie
 
Camionasul, de greutate $7$, are de ales intre doua rute: $1$, $2$, $5$, $6$ si $1$, $3$, $4$, $6$. In prima ruta, exista doua drumuri cu rezistenta mai mica decat $7$, drumurile $2$ - $5$ si $5$ - $6$, pe cand in a doua ruta, exista un singur drum cu rezistenta mai mica decat $7$, drumul $4$ - $6$.
 

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

9215