San Francisco

Time limit: 0.5s Memory limit: 64MB Input: Output:

Ernest este un prea cunoscut călător în timp, iscusit la afaceri. De această dată, el se află în California anului 1851 în plina "Goană după Aur". Rețeaua de drumuri dintre orașele Californiei poate fi reprezentată ca un multigraf ponderat (cu costuri pe muchii) neorientat cu NN noduri (orașe) și MM muchii (drumuri). Ernest vrea să transporte aurul descoperit de el pe o rută din orașul 11 până în orașul 22 folosind rețeaua de drumuri. O rută de la un oraș xx la un oraș yy reprezintă o succesiune de drumuri care începe în xx și se termină în yy. Distanța unei rute este egală cu suma distanțelor drumurilor ce o formează.

El este un bun istoric și știe despre incendiul din San Francisco ce urmează să aibă loc. Din păcate, el nu este și un bun geograf și nu știe care dintre orașe este San Francisco, neștiind astfel nici drumurile care ar putea fi afectate de incendiu.

Cerință

Ernest este precaut și vrea să își diversifice rutele, dar fără să sacrifice din eficiență. Astfel, el vrea să îl ajutați să afle, pentru fiecare drum dintre 22 orașe, câte rute de distanță minimă dintre orașele 11 și 22 folosesc acest drum, modulo 998 244 353998 \ 244 \ 353.

Date de intrare

Pe prima linie se găsesc două numere naturale, NN și MM. Pe următoarele MM linii se află drumurile dintre orașe sub forma xix_i, yiy_i, did_i, reprezentând faptul că orașele xix_i și yiy_i sunt conectate de un drum de distanță did_i.

Date de ieșire

Pentru a reduce dimensiunea fișierului de output, se va afișa un singur număr, suma răspunsurilor pentru toate cele MM muchii, calculată modulo 998 244 353998 \ 244 \ 353.

Restricții și precizări

  • 2N100 0002 \leq N \leq 100 \ 000;
  • 1M200 0001 \leq M \leq 200 \ 000;
  • 1xi,yiN,i{1,2,,M}1 \leq x_i, y_i \leq N, \forall i \in \{1, 2, \dots, M\};
  • 1di2 000 000 000,i{1,2,,M}1 \leq d_i \leq 2 \ 000 \ 000 \ 000, \forall i \in \{1, 2, \dots, M\};
  • Orașele sunt numerotate de la 11 la NN;
  • Între două noduri uu și vv pot exista mai multe muchii;
  • Pentru teste valorând 3333 de puncte, 1N1 0001 \leq N \leq 1 \ 000, 1M5 0001 \leq M \leq 5 \ 000;
  • Pentru restul de 6767 de puncte, nu există restricții suplimentare.

Exemplu

stdin

4 5
1 3 5
3 4 6
4 2 7
2 1 18
2 3 12

stdout

2

Explicație

Există o singură rută de la orașul 11 la orașul 22 cu distanța 1717 care folosește 22 drumuri.

Log in or sign up to be able to send submissions!