Bittimaassa on $n$ kaupunkia, joiden välillä on $m$ tietä. Yksi kaupungeista on pääkaupunki.

Tehtäväsi on laskea, montako erilaista tapaa on poistaa joukko teitä niin, että etäisyydet pääkaupungista kaikkiin muihin kaupunkeihin säilyvät samoina.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $m$: kaupunkien määrä ja teiden määrä. Kaupungit on numeroitu $1,2,\ldots,n$, ja kaupunki $1$ on pääkaupunki.

Sitten syötteessä on $m$ riviä, joista jokainen kuvaa yhden tien. Jokaisella rivillä on kolme kokonaislukua $a$, $b$ ja $c$: tie on kaupunkien $a$ ja $b$ välillä ja sen pituus on $c$. Kaikki tiet ovat kaksisuuntaisia.

Voit olettaa, että kaikkien kaupunkien välillä on jokin reitti.

Tuloste

Tulosta yksi kokonaisluku: vastaus tehtävään. Koska vastaus voi olla suuri, tulosta se modulo $10^9+7$.

Rajat

• $1 \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 2 5
1 3 1
1 4 7
2 4 3
3 4 2

Tuloste:

4

Selitys: voit säilyttää kaikki tiet, poistaa 3-painoisen tien, poistaa 7-painoisen tien tai poistaa 3-painoisen ja 7-painoisen tien.