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