Autobuze3

autobuze3

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

A venit vara, iar soferii de autobuz sunt in extaz deoarece multa lume o sa se duca in vacanta cu autobuzele acestora. Tara in care traiesc acestia este compusa din $N$ orase conectate intre ele prin $M$ autostrazi de mare viteza cum doar in Romania mai vezi. Si pentru ca se aseamana foarte mult cu cele din Romania fiecare autostrada are o taxa pe care trebuie sa o platesti daca vrei sa circuli pe ea.
 
Exista doua tipuri de operatii:
$1. Drive b x y$ - Autobuzul $b$ trece din orasul $x$ in orasul $y$, cu conditia ca autobuzul $b$ sa fie in orasul $x$, sa existe cel putin un sofer in acesta si sa existe o autostrada construita intre orasele $x$ si $y$. Costul operatiei este taxa autostrazii.
$2. Move s x y$ - Soferul $s$ trece din autobuzul $x$ in autobuzul $y$, cu conditia ca soferul $s$ sa se afle in autobuzul $x$ iar autobuzele $x$ si $y$ sa fie in acelasi oras. Costul operatiei este $0$.
 
Intr-un oras pot fi oricate autobuze iar in oricare autobuz incap toti cei $N$ soferi. Initial soferul $i$ se afla in autobuzul $i$, in orasul $i$.
 
Pentru ca soferii vor sa isi puna la punct planul de a castiga cat mai multi bani pe vara aceasta, ei trebuie sa se stranga toti intr-un singur autobuz ca sa discute. Pentru ca ei nu vor sa plateasca prea mult acestia va roaga sa le spuneti costul minim ca toti soferii sa ajunga intr-un singur autobuz si o succesiune de operatii ([$1$] si $2$) astfel incat totii soferii sa ajunga in acelasi autobuz cu costul minim de mai sus, si, in plus, niciun sofer sa nu-si schimbe autobuzul mai mult de $25$ de ori.

Poveste şi cerinţă...

h2. Date de intrare

Fisierul de intrare $autobuze3.in$ va contine pe prima linie un numar intreg $T$, reprezentand numarul de teste. Pe prima linie a fiecarui test se vor afla doua numere intregi $N$ si $M$ care reprezinta numarul de orase, respective numarul de autostrazi. Pe urmatoarele $M$ linii se vor afla cate trei numere intregi $x$, $y$ si $c$ cu semnificatia ca exista o autostrada intre orasele $x$ si $y$ cu taxa $c$.

Fişierul de intrare $autobuze3.in$ ...

h2. Date de ieşire

Fisierul de iesire $autobuze3.out$ va contine raspunsurile pentru cele $T$ teste. Pe prima linie a fiecarui test se afla un numar intreg $Cmin$ ce reprezinta costul minim ca toti soferii sa ajunga intr-un singur autobuz. Pe urmatoarele linii se vor afisa operatiile, cate una pe linie. La sfarsitul operatiilor veti afisa cuvantul $"Gata"$ pe o linie noua.

În fişierul de ieşire $autobuze3.out$ ...

h2. Restricţii

* Pentru toate testele de la evaluare $T = 10$
* $1 ≤ N ≤ 2*10^5^$
* $1 ≤ M ≤ 4*10^5^$
* $0 ≤$ taxa unei autostrazi $≤ 10^9^$
* $Cmin ≤ 2*10^9^$
* Graful este conex!
 

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

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

| 2
  3 3
  1 2 1
  1 3 1
  2 3 2
  4 5
  1 2 1
  1 3 1
  2 3 2
  2 4 1
  3 4 2
| 2
  Drive 2 2 1
  Drive 3 3 1
  Move 2 2 1
  Move 3 3 1
  Gata
  3
  Drive 4 4 2
  Drive 3 3 1
  Move 4 4 2
  Drive 2 2 1
  Move 2 2 1
  Move 4 2 1
  Move 3 3 1
  Gata

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

|
h3. Explicaţie

In pimul test, soferii $2$ si $3$ se duc in orasul $1$ cu un cost total de $2$.
In al doilea test, soferii se strang in orasul $1$. Soferul $4$ se duce in orasul $2$, se muta in autobuzul $2$ si se duce impreuna cu soferul $2$ in orasul $1$, soferul 3 se duce in orasul $1$. Costul total este de $1+1+1=3$.

...

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