CSES - Leirikisa 2 - Tieverkko
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Bittimaassa on nn kaupunkia, joiden välillä on mm 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 nn ja mm: kaupunkien määrä ja teiden määrä. Kaupungit on numeroitu 1,2,,n1,2,\ldots,n, ja kaupunki 11 on pääkaupunki.

Sitten syötteessä on mm riviä, joista jokainen kuvaa yhden tien. Jokaisella rivillä on kolme kokonaislukua aa, bb ja cc: tie on kaupunkien aa ja bb välillä ja sen pituus on cc. 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 109+710^9+7.

Rajat

  • 1n1051 \le n \le 10^5
  • 1m21051 \le m \le 2 \cdot 10^5
  • 1a,bn1 \le a,b \le n
  • 1c1091 \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.