==Include(page="template/taskheader" task_id="distante")==
 
==Include(page="template/raw")==
 
Distante
 
 
 
Un bun prieten de-al lui Zaharel, Bronzarel este la spital bolnav de tifos. Fiind buni prieteni, Zaharel se duce sa-l viziteze pe acesta. Ultima data cand a fost in vizita, Bronzarel desenase pe peretii spitalului mai multe grafuri neorientate conexe cu costuri (da, si Bronzarel este pasionat de informatica!) si mai mult de atat calculase pentru fiecare dintre acestea distantele minime de la un nod sursa ales la toate celelalte. Zaharel, curios ca intotdeana, a decis ca vrea sa vada daca Bronzarel delireaza sau nu si si-a notat pe o foaie de hartie ceea ce scrisese acesta pe pereti. Cand a ajuns acasa, el s-a decis sa vada pentru care din grafuri distantele minime calculate de Bronzarel erau corecte.
 
h2. Cerinta
 
Scrieti un program care-l ajuta pe Zaharel sa determine pentru fiecare graf daca distantele minime au fost calculate correct.
 
 
 
Date de intare
 
Pe prima linie din fisierul de intrare distante.in se va gasi un numar T, reprezetand cate grafuri sunt pe foaie. Urmatoarele linii vor descrie succesiv cate un graf. Prima linie din descrierea unui graf va contine numerele N, M, si S reprezentand numarul de noduri , numarul de muchii si, respective, nodul sursa de la care se calculeaza distantele minime. A doua linie din descriere contine N elemente D[1] D[2] ... D[N] reprezentand distantele minime calculate de Bronzarel. Urmatoarele M linii vor contine cate trei numere naturale a b c reprezentand faptul ca exista o muchie de cost c de la a la b.
 
h2. Date de Iesire
 
Fisierul de iesire distante.out va contine T linii, fiecare cu cate un cuvant: "DA" daca distantele minime au fost calculate correct pentru graful respective, sau "NU" altfel.
 
h2. Restrictii
 
S 0 <= T <= 10
 
S 1 <= a,b,S <= N <= 50.000
 
S 0 <= M <= 100.000
 
S 0 <= c <= 1.000
 
h2. Exemplu
 
 
|distante.in |distante.out |
 
|2 |DA |
| | |
|5 6 1 |NU |
| | |
|0 1 7 3 6 | |
| | |
|1 2 1 | |
| | |
|1 3 7 | |
| | |
|1 4 3 | |
| | |
|3 4 4 | |
| | |
|2 5 5 | |
| | |
|4 5 6 | |
| | |
|4 4 2 | |
| | |
|1 0 2 3 | |
| | |
|1 2 1 | |
| | |
|2 3 1 | |
| | |
|2 4 1 | |
| | |
|3 4 1 | |
 
 

==Include(page="template/taskheader" task_id="distante")==
 
Un bun prieten de-al lui Zaharel, Bronzarel este la spital bolnav de tifos. Fiind buni prieteni, Zaharel se duce sa-l viziteze pe acesta. Ultima data cand a fost in vizita, Bronzarel desenase pe peretii spitalului mai multe grafuri neorientate conexe cu costuri (da, si Bronzarel este pasionat de informatica!) si mai mult de atat calculase pentru fiecare dintre acestea distantele minime de la un nod sursa ales la toate celelalte. Zaharel, curios ca intotdeana, a decis ca vrea sa vada daca Bronzarel delireaza sau nu si si-a notat pe o foaie de hartie ceea ce scrisese acesta pe pereti. Cand a ajuns acasa, el s-a decis sa vada pentru care din grafuri distantele minime calculate de Bronzarel erau corecte.
 
h2. Cerinta
 
Scrieti un program care-l ajuta pe Zaharel sa determine pentru fiecare graf daca distantele minime au fost calculate correct.
 
h2. Date de intare
 
Pe prima linie din fisierul de intrare $distante.in$ se va gasi un numar {$T$}, reprezetand cate grafuri sunt pe foaie. Urmatoarele linii vor descrie succesiv cate un graf. Prima linie din descrierea unui graf va contine numerele {$N$}, {$M$}, si $S$ reprezentand numarul de noduri , numarul de muchii si, respectiv, nodul sursa de la care se calculeaza distantele minime. A doua linie din descriere contine $N$ elemente $D{~1~} D{~2~} ... D{~N~}$ reprezentand distantele minime calculate de Bronzarel. Urmatoarele $M$ linii vor contine cate trei numere naturale $a b c$ reprezentand faptul ca exista o muchie de cost $c$ de la $a$ la {$b$}.
 
h2. Date de Iesire
 
Fisierul de iesire $distante.out$ va contine $T$ linii, fiecare cu cate un cuvant: $DA$ daca distantele minime au fost calculate correct pentru graful respective, sau $NU$ altfel.
 
h2. Restrictii
 
* $0 ≤ T ≤ 10$
* $1 ≤ a,b,S ≤ N ≤ 50.000$
* $0 ≤ M ≤ 100.000$
* $0 ≤ c ≤ 1.000$
 
h2. Exemplu
 
 
table(example). |_. distante.in |_. distante.out |
| 2
5 6 1
0 1 7 3 6
1 2 1
1 3 7
1 4 3
3 4 4
2 5 5
4 5 6
4 4 2
1 0 2 3
1 2 1
2 3 1
2 4 1
3 4 1
| DA
NU |
 
==Include(page="template/taskfooter" task_id="distante")==

==Include(page="template/taskfooter" task_id="distante")==

640