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

==Include(page="template/raw")==
 

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).

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

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

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.

4 3 5 | 2 |
==Include(page="template/taskfooter" task_id="algola")==

427