色と経路

頂点が $V$ 個、辺が $E$ 本の無向グラフがある。各辺の色は $1$ 番から $K$ 番のいずれかである。

頂点 $1$ から頂点 $V$ へ行く経路のコストは次の通りである。

同じ頂点や辺を複数回通ってもよい。同じ辺を複数回通った場合、通った回数だけ数える。

頂点 $1$ から頂点 $V$ へ行く経路の最小コストを求めよ。

入力は以下の形式で与えられる。

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

各テストケースについて、最小コストを $1$ 行に出力せよ。

• $1\leq T\leq100\,000$.
• $2\leq V\leq100\,000$; $1\le E\le 100$; .