== include(page="template/taskheader" task_id="autobuze3") ==
Por Costel si cei N-1 prieteni ai sai porci s-au facut soferi de autobuz ca sa-si castige coceanul. Porcii si-au terminat tura pe ziua de azi si vor sa se intalneasca ca sa-si imparta cocenii (ce prieteni buni!). Ei traisec in Orasul Porcilor, un oras format din N statii de autobuze legate intre ele prin M strazi bidirectionale, de lungimi diferite. Cei N porci, impreuna cu cele N autobuze ale lor, se gasesc toti in oras. Initial al i-lea porc se gaseste in al i-lea autobuz in a i-a statie de autobuz din oras. Obiectivul vostru este sa aduceti toti cei N porci in acelasi autobuz (autobuzele din Orasul Porcilor folosesc fizica nucleara pentru a putea face ca oricati porci grasi sa incape intr-un singur autobuz).
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 pe care le puteti efectua:
$1. Drive b x y$ - Autobuzul $b$ trece din statia $x$ in statia $y$, cu conditia ca autobuzul $b$ sa fie in statia $x$, sa existe cel putin un porc in acesta (care sa-l conduca) si sa existe o strada intre statiile $x$ si $y$. Costul operatiei este lungimea strazii.
$2. Move p x y$ - porcul $p$ trece din autobuzul $x$ in autobuzul $y$, cu conditia ca porcul $p$ sa se afle in autobuzul $x$ iar autobuzele $x$ si $y$ sa fie in aceeasi statie. Costul operatiei este $0$.
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$.
Asa cum am spus mai sus, intr-un autobuz incap oricati porci. De asemenea, intr-o statie incap oricate autobuze.
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$.
Porcii, solidari fiind, vor sa minimizeze distanta totala parcursa de toti la un loc. In plus, deoarece toti porcii sunt grasi si nu au chef sa se miste, trebuie ca un porc sa nu schimbe autobuzul de mai multe de $25$ ori.
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.
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 statii, respective numarul de strazi. Pe urmatoarele $M$ linii se vor afla cate trei numere intregi $x$, $y$ si $c$ cu semnificatia ca exista o strada intre statiile $x$ si $y$ cu lungimea $c$.
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$.
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 porcii 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.
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.
h2. Restricţii
* Pentru toate testele de la evaluare $T = 10$
* $1 ≤ N ≤ 2*10^5^$
* $1 ≤ M ≤ 4*10^5^$
* $-10^9^ ≤$ taxa unei strazi $≤ 10^9^$
* $0 ≤$ taxa unei autostrazi $≤ 10^9^$
* $Cmin ≤ 2*10^9^$
* Graful este conex!
h2. Exemplu
h3. Explicaţie
In primul test, porcii $2$ si $3$ se duc in statia $1$ unde intra in autobuzul lui Por Costel cu un cost total de $2$.
In al doilea test, porcii se strang in statia $1$. Porcul $4$ se duce in statia $2$, se muta in autobuzul $2$ si se duce impreuna cu porcul $2$ in statia $1$, porcul 3 se duce in statia $1$. Si de data aceasta, Por Costel sta degeaba si asteapta. Costul total este de $1+1+1=3$.
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") ==
