==Include(page="template/taskheader" task_id="algola")==
 
==Include(page="template/raw")==
 
algola
 
In cadrul organizatiei Algola s-a declarat stare de urgenta. Toti membrii sai, aflati in diferite orase din tara, trebuie sa ajunga cat mai rapid la sediul central. Cele N orase de pe harta tarii sunt numerotate cu numerele de la 1 la N, orasul 1 fiind locatia sediul central. Strazile ce conecteaza orasele sunt bidirectionale si fiecare dintre strazi poate fi parcursa intr-o unitate de timp de oricare membru Algola. Fiecare strada are o limita de siguranta care indica numarul maxim de membri ce pot circula intr-o unitate de timp pe acea strada. Parcurgerea unei strazi poate incepe numai la momente de timp intregi.
 
h2. Cerinta
 
Fiind data harta oraselor, precum si numarul de membrii ai organizatiei aflati in fiecare oras, sa se calculeze timpul minim T necesar acestora pentru a ajunge la sediul central (T va fi momentul la care ajunge ultimul membru la sediul central).
 
h2. Date de Intrare
 
Prima linie a fisierului algola.in contine doua numere intregi separate printr-un spatiu, N si M, reprezentand numarul de orase de pe harta si numarul de strazi dintre ele. Pe cea de-a doua linie se vor afla N numere separate prin spatii, A[1] A[2] ... A[N,] unde A[i] reprezinta numarul de membri din orasul i. Urmatoarele M linii contin cate trei numere intregi separate prin spatii, X Y L, cu semnificatia: intre orasele X si Y exista o strada a carei limita de siguranta este L.
 
h2. Date de Iesire
 
Fisierul de iesire algola.out va contine o singura linie numarul T reprezentand timpul minim in care membrii organizatiei ajung la sediul central.
 
h2. Restrictii si precizari
 
S 1 <= N <= 50
 
S 1 <= M <= 300
 
S Timpul de parcurgere al unui oras este 0
 
S Totii membrii vor putea ajunge la sediu central
 
S Limitele de siguranta ale strazilor sunt numere intregi pozitive din intervalul [1,10]
 
S Toti membrii organizatiei afla de starea de urgenta la momentul 0
 
S Organizatia are cel mult 50 de membri
 
S Membrii organizatiei pot ramane in orice oras pe o perioada nelimitata de timp
 
S Pentru 20% din teste drumul de la fiecare oras la sediu este unic; pentru inca 30% din teste numarul total de membri ai organizatiei va fi maxim 4
 
h2. Exemplu
 
 
|algola.in |algola.out |
 
|4 4 |2 |
| | |
|0 5 6 5 | |
| | |
|1 2 3 | |
| | |
|1 3 5 | |
| | |
|4 2 2 | |
| | |
|4 3 5 | |

==Include(page="template/taskheader" task_id="algola")==
 
In cadrul organizatiei Algola s-a declarat stare de urgenta. Toti membrii sai, aflati in diferite orase din tara, trebuie sa ajunga cat mai rapid la sediul central. Cele $N$ orase de pe harta tarii sunt numerotate cu numerele de la $1$ la $N$, orasul $1$ fiind locatia sediului central. Strazile ce conecteaza orasele sunt bidirectionale si fiecare dintre strazi poate fi parcursa intr-o unitate de timp de oricare membru Algola. Fiecare strada are o limita de siguranta care indica numarul maxim de membri ce pot circula intr-o unitate de timp pe acea strada. Parcurgerea unei strazi poate incepe numai la momente de timp intregi.
 
h2. Cerinta
 
Fiind data harta oraselor, precum si numarul de membrii ai organizatiei aflati in fiecare oras, sa se calculeze timpul minim $T$ necesar acestora pentru a ajunge la sediul central ({$T$} va fi momentul la care ajunge ultimul membru la sediul central).
 
h2. Date de intrare
 
Prima linie a fisierului $algola.in$ contine doua numere intregi separate printr-un spatiu, $N$ si $M$, reprezentand numarul de orase de pe harta si numarul de strazi dintre ele. Pe cea de-a doua linie se vor afla N numere separate prin spatii, $A{~1~} A{~2~} ... A{~N~}$ unde $A{~i~}$ reprezinta numarul de membri din orasul $i$. Urmatoarele $M$ linii contin cate trei numere intregi separate prin spatii, $X Y L$, cu semnificatia: intre orasele $X$ si $Y$ exista o strada a carei limita de siguranta este $L$.
 
h2. Date de iesire
 
Fisierul de iesire $algola.out$ va contine o singura linie numarul $T$ reprezentand timpul minim in care membrii organizatiei ajung la sediul central.
 
h2. Restrictii si precizari
 
* $1 ≤ N ≤ 50$
* $1 ≤ M ≤ 300$
* Timpul de parcurgere al unui oras este $0$
* Totii membrii vor putea ajunge la sediu central
* Limitele de siguranta ale strazilor sunt numere intregi pozitive din intervalul $[1,10]$
* Toti membrii organizatiei afla de starea de urgenta la momentul $0$
* Organizatia are cel mult $50$ de membri
* Membrii organizatiei pot ramane in orice oras pe o perioada nelimitata de timp
* Pentru $20%$ din teste drumul de la fiecare oras la sediu este unic; pentru inca $30%$ din teste numarul total de membri ai organizatiei va fi maxim $4$
 
h2. Exemplu
 
 
table(example). |_. algola.in |_. algola.out |
| 4 4
0 5 6 5
1 2 3
1 3 5
4 2 2
4 3 5 | 2 |
 
==Include(page="template/taskfooter" task_id="algola")==

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

427