FMI NO STRESS 12 | San Francisco

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 $N$ noduri (orașe) și $M$ muchii (drumuri). Ernest vrea să transporte aurul descoperit de el pe o rută din orașul $1$ până în orașul $2$ folosind rețeaua de drumuri. O rută de la un oraș $x$ la un oraș $y$ reprezintă o succesiune de drumuri care începe în $x$ și se termină în $y$. 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 $2$ orașe, câte rute de distanță minimă dintre orașele $1$ și $2$ folosesc acest drum, modulo $998 \ 244 \ 353$.

Date de intrare

Pe prima linie se găsesc două numere naturale, $N$ și $M$. Pe următoarele $M$ linii se află drumurile dintre orașe sub forma $x_i$, $y_i$, $d_i$, reprezentând faptul că orașele $x_i$ și $y_i$ sunt conectate de un drum de distanță $d_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 $M$ muchii, calculată modulo $998 \ 244 \ 353$.

Restricții și precizări

• $2 \leq N \leq 100 \ 000$;
• $1 \leq M \leq 200 \ 000$;
• $1 \leq x_i, y_i \leq N, \forall i \in \{1, 2, \dots, M\}$;
• $1 \leq d_i \leq 2 \ 000 \ 000 \ 000, \forall i \in \{1, 2, \dots, M\}$;
• Orașele sunt numerotate de la $1$ la $N$;
• Între două noduri $u$ și $v$ pot exista mai multe muchii;
• Pentru teste valorând $33$ de puncte, $1 \leq N \leq 1 \ 000$, $1 \leq M \leq 5 \ 000$;
• Pentru restul de $67$ 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 $1$ la orașul $2$ cu distanța $17$ care folosește $2$ drumuri.