Zadanie

Ideme cestovať

Počet bodov: 55, časový limit: 1000ms

Kubík je veľký pocestný obchodník s elektronikou. Jeho povolanie od neho vyžaduje nadšenie, veľkú flexibilitu a obetavosť. Nadovšetko od neho však vyžaduje schopnosť prepraviť sa medzi ľubovoľnými dvoma mestami v priebehu jediného dňa a po poslednom fiasku s meškajúcim vlakom sa Kubík napokon rozhodol zaobstarať si novú Teslu. Môže si to predsa dovoliť! Nechce však ani plytvať peniazami a zbytočne si kúpiť priveľkú batériu. Počas jedného dňa je ochotný sa najviac \(C\) krát zastaviť na nabíjacej stanici, pričom sa vždy zastaví nabiť pred tým, ako v ten deň vyrazí na cestu medzi mestami. Mestá tvoria súvislý graf s \(N\) vrcholmi a \(M\) ohodnotenými hranami a v každom meste je nabíjacia stanica, na ktorej si môže batériu nabiť na ľubovoľnú úroveň.

Aký najmenší dojazd môže mať batéria, aby sa Kubík vedel dostať medzi ľubovoľnými dvoma mestami na najviac \(C\) nabití?

Vstup a výstup

Na prvom riadku vstupu je jedno celé číslo \(T\) - počet otázok.

Nasleduje \(T\) otázok. Pre každú otázku: Sú na prvom riadku \(3\) celé čísla \(N\), \(C\) a \(M\). Nasleduje \(M\) riadkov, na \(i\)-tom riadku sú \(3\) celé čísla \(a_i\), \(b_i\) a \(d_i\), ktoré reprezentujú cestu dĺžky \(d_i\) medzi mestami \(a_i\) a \(b_i\). Každá neusporiadaná dvojica \((a_i,b_i)\) sa vyskytne najviac raz, pričom pre každé \(i\) je \(a_i\) rôzne od \(b_i\).

Vo všetkých testovacích sadách platí \(0 \leq T \leq 10\), \(0 \leq N \leq 100\), \(0 \leq C \leq 1000\), pričom \(0 \leq a_i, b_i \leq N-1\) a \(0 \leq d_i \leq 10^9\) pre všetky \(i\). Navyše, v prvých 2 sadách budú \(0 \leq d_i \leq 100\) a \(N\) bude v jednotlivých sadách postupne najviac \(5, 10, 30, 50, 100\). Celkovo bude teda 5 sád, každá za 20% celkového počtou bodov.

Na výstup vypíšte \(T\) riadkov, na každom riadku najmenšiu kapacitu batérie pre prislúchajúcu otázku.

Príklady

Input:

2
4 2 4
0 1 100
3 0 400
1 2 200
2 3 300
10 2 15
3 8 355
4 9 113
5 7 235
7 9 979
8 5 462
0 5 411
0 1 113
1 2 314
9 6 402
6 8 431
2 3 271
3 4 141
4 0 173
1 6 855
2 7 921

Output:

300
688