색깔과 경로

정점이 $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$; .