În cadrul organizaţiei Algola s-a declarat stare de urgenţă. Toţi membrii săi, aflaţi în diferite oraşe din ţară, trebuie să ajungă cât mai rapid la sediul central. Cele N oraşe de pe harta ţării sunt numerotate cu numerele de la 1 la N, oraşul 1 fiind locaţia sediul central. Străzile ce conectează oraşele sunt bidirecţionale şi fiecare dintre străzi poate fi parcursă într-o unitate de timp de oricare membru Algola. Fiecare stradă are o limita de siguranţă care indică numărul maxim de membri ce pot circula într-o unitate de timp pe acea stradă. Parcurgerea unei străzi poate începe numai la momente de timp întregi.

Cerinţă

Fiind dată harta oraşelor, precum şi numărul de membrii ai organizaţiei aflaţi în fiecare oraş, să 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).

Date de intrare

Prima linie a fişierului algola.in conţine două numere întregi separate printr-un spaţiu, N şi M, reprezentând numărul de oraşe de pe hartă şi numărul de străzi dintre ele. Pe cea de-a doua linie se vor afla N numere separate prin spaţii, A1 A2 … AN, unde Ai reprezintă numărul de membri din oraşul i. Următoarele M linii conţin câte trei numere întregi separate prin spaţii, X Y L, cu semnificaţia: între oraşele X şi Y există o stradă a cărei limită de siguranţă este L.

Date de ieşire

Fişierul de ieşire algola.out va conţine o singură linie numărul T reprezentând timpul minim în care membrii organizaţiei ajung la sediul central.

Restricţii

1 ≤ N ≤ 50
1 ≤ M ≤ 300
Timpul de parcurgere al unui oraş este 0
Toţii membrii vor putea ajunge la sediu central
Limitele de sigurantă ale străzilor sunt numere întregi pozitive din intervalul [1,10]
Toţi membrii organizaţiei află de starea de urgenţă la momentul 0
Organizaţia are cel mult 50 de membri
Membrii organizaţiei pot rămâne în orice oraş pe o perioadă nelimitată de timp
Pentru 20% din teste drumul de la fiecare oraş la sediu este unic; pentru încă 30% din teste numărul total de membri ai organizaţiei va fi maxim 4

Exemple

algola.in	algola.out
4 4 0 5 6 5 1 2 3 1 3 5 4 2 2 4 3 5	2

autor: Silviu Gănceanu

propunător: Prof. Emanuela Cerchez

Liceul de Informatica ″Grigore Moisil″

emanuela.cerchez@gmail.com