颜色与路径

有一个包含 $V$ 个顶点、$E$ 条边的无向图。每条边的颜色为 $1$ 号到 $K$ 号中的一种。

从 $1$ 号顶点到 $V$ 号顶点的路径的代价如下：

可以多次经过同一个顶点或同一条边。若多次经过同一条边，则按经过的次数计算。

求从 $1$ 号顶点到 $V$ 号顶点的路径的最小代价。

输入按以下格式给出。

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

对于每个测试用例，在一行中输出最小代价。

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