IOI-maa koostuu $N$ kaupungista, jotka on numeroitu kaupungista $1$ kaupunkiin $N$, ja kaupunkeja yhdistävät tiet. IOI-maassa on $K$ tietä, ja jokainen tie yhdistää $2$ eri kaupunkia. Autot voivat kulkea teitä pitkin vapaasti molempiin suuntiin, mutta kaupungista toiseen ei voi kulkea muuten kuin teitä pitkin.

IOI-maan kaupungissa $1$ asuva JOI-kun päätti mennä taksilla kaupungissa $N$ asuvan isoäitinsä luo. IOI-maassa on $N$ taksiyhtiötä, taksiyhtiöstä $1$ taksiyhtiöön $N$. IOI-maan taksiyhtiöillä on seuraavat hieman erikoiset säännöt:

• Taksiyhtiön $i$ taksiin voi nousta vain kaupungissa $i$.
• Taksiyhtiön $i$ taksin hinta on $C_i$ kuljetusta matkasta riippumatta.
• Taksiyhtiön $i$ taksi voi kyytiin nousemisen jälkeen kulkea peräkkäin enintään $R_i$ tietä pitkin.

Jos esimerkiksi $R_1 = 2$, kaupungista $1$ taksiyhtiön $1$ taksiin noustessa voidaan kulkea enintään $2$ tietä, joten $3$:n tai useamman tien kulkemiseksi on vaihdettava taksia jossakin matkan varrella olevassa kaupungissa.

JOI-kun ei voi nousta taksiin eikä poistua taksista missään muualla kuin kaupungissa. Hän ei myöskään voi käyttää mitään muuta kulkuvälinettä kuin taksia. Kirjoita ohjelma, joka etsii pienimmän mahdollisen kokonaishinnan, jolla JOI-kun pääsee kaupunkiin $N$.

Syöte

Syöte koostuu $1 + N + K$ rivistä.

$1$. rivillä on $2$ välilyönnillä erotettua kokonaislukua $N, K$ ($2 \le N \le 5000$, $N - 1 \le K \le 10000$). Tämä tarkoittaa, että IOI-maa koostuu $N$ kaupungista ja että IOI-maan teiden lukumäärä on $K$.

Seuraavien $N$ rivin $i$:nnellä rivillä ($1 \le i \le N$) on $2$ välilyönnillä erotettua kokonaislukua $C_i, R_i$ ($1 \le C_i \le 10000$, $1 \le R_i \le N$). Tämä tarkoittaa, että taksiyhtiön $i$ taksin hinta on $C_i$ ja että sillä voi kyytiin nousemisen jälkeen kulkea peräkkäin enintään $R_i$ tietä.

Seuraavien $K$ rivin $j$:nnellä rivillä ($1 \le j \le K$) on $2$ eri välilyönnillä erotettua kokonaislukua $A_j, B_j$ ($1 \le A_j < B_j \le N$). Tämä tarkoittaa, että kaupungin $A_j$ ja kaupungin $B_j$ välillä on tie. Sama pari $(A_j, B_j)$ ei esiinny $2$ kertaa tai useammin.

Annetussa syötteessä on taattu, että mistä tahansa kaupungista pääsee mihin tahansa toiseen kaupunkiin vaihtamalla taksia.

Tuloste

Tulosta $1$ riville kokonaisluku, joka ilmaisee pienimmän mahdollisen kokonaishinnan, jolla JOI-kun pääsee kaupungista $1$ kaupunkiin $N$.

Esimerkit

Syöte 1

6 6
400 2
200 1
600 3
1000 1
300 5
700 4
1 2
2 3
3 6
4 6
1 5
2 4

Tuloste 1

700

Huomautus

Yllä oleva esimerkki vastaa seuraavaa kuvaa. Ympyrät esittävät kaupunkeja ja viivat teitä.

Tässä esimerkissä JOI-kun pääsee kaupunkiin $6$ pienimmällä mahdollisella hinnalla toimimalla seuraavasti:

• Nousee taksiin kaupungissa $1$ ja ajaa kaupunkiin $5$. (Hinta $400$)
• Nousee taksiin kaupungissa $5$ ja ajaa kaupunkiin $6$. (Hinta $300$)

Koska kokonaishinta tällä reitillä on $400 + 300 = 700$, tulostetaan $700$.