Tutkimus

• Time limit: 1.00 s
• Memory limit: 128 MB

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