rutier

Transport Rutier

== include(page="template/taskheader" task_id="rutier") ==

Poveste si cerinta...

Ministrul Transportului, Braian Tasescu, a ajuns la concluzia ca are nevoie de o crestere a popularitatii sale pentru a aspira la functia de presedinte al tarii. De aceea, el vrea sa puna la punct un program prin care incearca intretinerea cat mai buna a unui sistem de transport rutier vital tarii.
 
Deocamdata el este interesat de cele mai importante $N$ orase ale tarii si vrea ca sistemul de transport sa fie format din $N-1$ strazi astfel incat fiecare oras sa fie legat de capitala (orasul cu indicele $1$) si costul total de intretinere a strazilor sa fie cat mai mic. Desi el a gasit initial sistemul optim de transport, pe viitor se mai construiesc $M$ strazi noi intre cele $N$ orase asa ca de multe ori e mai bine sa modifici sistemul astfel incat costul intretinerii lui sa fie minim.

h2. Date de intrare

...

Prima linie a fisierului de intrare contine numarul intreg $N$ iar pe fiecare din urmatoarele $N-1$ linii se vor afla informatii despre sistemul initial, pe linia $i$ aflandu-se doua numere intregi $K$ si $C$, reprezentand orasul cel mai apropiat de capitala de care este legat orasul $i$ si respectiv costul anual de intretine a strazii care leaga cele doua orase. Daca un oras e legat direct de capitala atunci $K=1$.
 
Linia $N+1$ contine numarul $M$ iar urmatoarele $M$ linii contin 3 numere intregi $X$, $Y$, $C$, care reprezinta faptul ca tocmai a fost construit un drum intre orasele $X$ si $Y$ care are costul anual de intretinere $C$.

h2. Date de iesire

...

In fisierul de iesire se vor scrie $M$ linii, linia $i$ continand un numar intreg reprezentant costul intretinerii sistemului dupa ce au mai fost construite $i$ strazi.

h2. Restrictii

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

* $1 ≤ N ≤ 50.000$
* $1 ≤ M ≤ 150.000$
* costul anual de intretinere al oricarei strazi este un numar natural cel mult egal cu $1.000.000$

h2. Exemplu
table(example). |_. rutier.in |_. rutier.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 9
 1 4
 2 6
 1 10
 3 6
 3 7
 5 2
 2 3
 2 6
 6
 8 4 3
 3 1 3
 8 1 3
 3 7 6
 6 7 4
 5 2 2
| 37
 34
 33
 33
 30
 26

|

h3. Explicatie
 
...
 

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

3431