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.