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

Poveste şi cerinţă...

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 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. Initialsoferul 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 23 de ori.

h2. Date de intrare

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

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

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

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 <= 10^5
* 1 <= M <= 2*10^5
* … <= taxa unei autostrazi <= …
 

h2. Exemplu