Uolevi aikoo jälleen kerran matkustaa Syrjälästä Lehmälään mahdollisimman halvalla. Sinulle on annettu tiedot lennoista kaupunkien välillä ja tehtäväsi on selvittää seuraavat asiat:

• mikä on halvin lentoreitin hinta?
• montako hinnaltaan halvinta reittiä on olemassa? (modulo $10^9+7)$
• mikä on pienin mahdollinen määrä lentoja reitillä, jonka hinta on halvin?
• mikä on suurin mahdollinen määrä lentoja reitillä, jonka hinta on halvin?

Huomaa, että lentojen muodostamassa verkossa voi olla syklejä.

Syöte

Syötteessä on ensin kaksi kokonaislukua $n$ ja $m$: kaupunkien määrä ja lentojen määrä. Kaupungit on numeroitu $1,2,\ldots,n$. Syrjälän numero on 1, ja Lehmälän numero on $n$.

Sitten syötteessä on $m$ riviä, jotka kuvaavat lennot. Jokaisella rivillä on kolme kokonaislukua $a$, $b$ ja $c$: kaupungista $a$ on lento kaupunkiin $b$ hintaan $c$. Kaikki lennot ovat yksisuuntaisia.

Voit olettaa, että on olemassa ainakin yksi halutunlainen reitti.

Tuloste

Tulosta neljä kokonaislukua tehtävänannon mukaisesti.

Rajat

• $2 \le n \le 10^5$
• $1 \le m \le 2 \cdot 10^5$
• $1 \le a,b \le n$
• $1 \le c \le 10^9$

Esimerkki

Syöte:

4 5
1 4 5
1 2 4
2 4 5
1 3 2
3 4 3

Tuloste:

5 2 1 2