== 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.

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

* $1 ≤ g ~i~ ≤ 1.000.000$

* $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!$

h3. Explicatie

Camionasul, de greutate $6$, 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 $6$, drumurile $2$ - $5$ si $5$ - $6$, pe cand in a doua ruta, exista un singur drum cu rezistenta mai mica decat $6$, drumul $4$ - $6$.

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