Colors and Paths

There is an undirected graph with $V$ vertices and $E$ edges. The color of each edge is one of colors $1$ through $K$.

The cost of a path from vertex $1$ to vertex $V$ is defined as follows.

The path may pass through the same vertex or edge multiple times. If the same edge is passed through multiple times, it is counted as many times as it is passed.

Find the minimum cost of a path from vertex $1$ to vertex $V$.

The input is given in the following format.

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

For each test case, print the minimum cost on a single line.

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