== include(page="template/taskheader" task_id="sistem3") ==

Poveste şi cerinţă...

Se da un graf *neorientat si conex* $G$ ce are $N$ noduri si $N$ muchii. Acest graf are asociat fiecarui nod o valoare numita $potential$. Astfel potentialul nodului i este $p[i]$. Deasemenea fiecare muchie are asociata si ea un cost $w$ (nu unic).
Definim gradientul unui nod $i$ suma $(p[j] - p[i]) * w[j][i]$ modulo $M$ ({$M$} dat) unde $j$ este un vecin de-al lui $i$, iar $w[j][i]$ este costul muchiei dintre $i$ si $j$.
 
Din pacate potentialele nodurilor au fost pierdute insa se cunosc gradientele si costurile de pe muchii. Vi se cere sa reconstituiti potentialele nodurilor stiind ca ele *aveau valori cuprinse intre 0 si $M - 1$*.

h2. Date de intrare

Fişierul de intrare $sistem3.in$ ...

Fişierul de intrare $sistem3.in$ va contine pe prima linie doua numere naturale $N$ si $M$ reprezentand numarul de noduri (si muchii) din graf, respectiv valoarea fata de care se face modulo.
 
Urmatoarele $N$ randuri vor contine fiecare $3$ numere naturale $x$, $y$ si $w$ cu semnificatia: exista o muchie intre nodul $x$ si nodul $y$ de cost $w$.
 
Urmatoarea si ultima linie va contine $N$ numere naturale, a $i$-a valoare reprezentand gradientul nodului $i$.

h2. Date de ieşire

În fişierul de ieşire $sistem3.out$ ...

În fişierul de ieşire $sistem3.out$ trebuie sa se gaseasca $N$ linii fiecare continand o valoare naturala intre $0$ si $M - 1$, acestea reprezentand in ordine potentialele nodurilor 1, 2, .., N.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100.000$
* $1 ≤ x, y ≤ N$
* $1 ≤ w ≤ M - 1$
* $2 ≤ M ≤ 46000$
* $*M e prim*$
* $0 ≤ gradientul oricarui nod ≤ M - 1$
* $Pentru 30% din teste N <= 100$
* $Pentru 50% din teste una din muchii este de forma x x w$

h2. Exemplu