== 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.

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$.

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. Initial soferul $i$ se afla in autobuzul $i$, in orasul $i$.

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.

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 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$.

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

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^$

* 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

h2. Exemplu

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$.

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. Cu un cost total de 1+1+1=3

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