h2. Date de ieşire

În fişierul de ieşire $harbingers.out$ trebuie sa se afle exact $N-1$ intregi. Al i-lea
 
The output file harbingers.out should consist of exactly one line containing N-1 integers.
The ith number represents the minimum time, in minutes, required to send a message from the
(i+1)th town to the capital.

În fişierul de ieşire $harbingers.out$ trebuie sa se afle exact $N-1$ intregi. Al $i$-lea numar reprezinta timpul minim, in minute, necesar pentru a trimite un mesaj de la orasul $(i+1)$ la capitala.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100 000$
* $0 ≤ S{~i~} ≤ 10^9^$
* $1 ≤ V{~i~} ≤ 10^9^$
* Lungimea oricarei poteci nu va depasi $10 000$
* Pentru 20% din teste, $N ≤ 2500$
* Pentru 50% din teste, fiecare oras se va invecina cu cel multe alte 2 orase (graful potecilor va fi un graf linie)

h2. Exemplu

h3. Explicaţie

...

Potecile si lungimile lor sunt prezentate in imaginea din stanga. Timpul necesar pentru pregatirea calatoriei si viteza mesagerilor sunt scrise intre paranteze.
Timpul minim pentru a trimite un mesaj de la orasul 5 la capitala este obtinut dupa cum urmeaza. Mesagerul din orasul 5 preia mesajul si paraseste orasul dupa 2 minute. Strabate o distanta de 4 kilometri in 120 de minute, inainte de a ajunge in orasul 2. Acolo lasa mesajul mesagerului din orasul respectiv. Acesta are nevoie de 26 de minute pentru a pregati calatoria si va merge pentru 180 de minute inainte sa ajunga la capitala.
Timpul total este deci 2 + 120 + 26 + 180 = 328.

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