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

Poveste şi cerinţă...

Se da un graf $G$ *neorientat si conex* cu $N$ noduri si $N$ muchii. Fiecare nod din acest graf are asociata o valoare numita $potential$. Potentialul nodului $i$ este $p[i]$. De asemenea fiecare muchie a grafului are asociat un cost.
Definim gradientul unui nod $i$ suma $(p[j] - p[i]) * w[j][i]$ modulo $M$ ({$M$} dat) unde $j$ este vecin de-al lui $i$, iar $w[j][i]$ este costul muchiei dintre $i$ si $j$.
 
Din pacate potentialele nodurilor au fost pierdute. Se cunosc insa gradientele pentru fiecare nod 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 cate $3$ numere naturale $x$, $y$ si $w$ cu semnificatia: exista o muchie intre nodul $x$ si nodul $y$ de cost $w$.
 
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

| 0
0
1

0
|
 
h3. Explicaţie
 
...

0 |
|5 5
2 4 4
3 5 4
3 1 3
4 1 4
1 5 4
4 1 2 2 1
| 0
4
4
3
0|

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

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