조이가 사는 도시에는 1부터 N까지 번호가 붙어있는 N개의 역과, 두 개의 역을 양방향으로 연결하는 M개의 철로가 있다.

i(1 ≦ i ≦ M)번째 철도 노선은 A_i번째 역과 B_i번째 역을 양방향으로 연결하며, 승차 운임은 C_i원이다.

조이는 S번째 역에서 살고 있으며, T번째 역에 있는 고등학교에 다니고 있다.

때문에 조이는 S번째 역과 T번째 역을 오가는 정기권을 구입하기로 결심했다.

정기권을 구입할 때는 S번째 역과 T번째 역을 연결하는 경로들 중 최소 비용인 경로를 하나 골라야 한다.

지정한 경로에 포함된 철도 노선은 양방향으로, 추가 비용을 들이지 않고 자유롭게 타고 다닐 수 있다.

조이는 U번째와 V번째 역에 있는 서점도 자주 이용하고 있다.

그래서 U번째 역과 V번째 역을 오갈 때 비용이 가능한 작아지도록 정기권을 구입하기로 했다.

여기서 U번째 역에서 V번째 역으로 이동할 때 드는 최소 비용은 다음과 같다.

먼저 U번째 역과 V번째 역을 연결하는 경로를 하나 선택한다.

이 경로에 포함된 철도 노선 i에서 지불해야하는 요금은,

• 철도 노선 i가 정기권에서 지정한 철도 노선에 포함 된 경우 0원

• 철도 노선 i가 정기권에서 지정한 철도 노선에 포함되지 않은 경우 C_i원

이 된다. 총 비용은 모든 철도 노선에 대한 비용의 합이며, 최소 비용은 모든 경로 중 비용의 최솟값이다.

정기권을 구입할 때 지정하는 경로를 잘 선택하여, U번째 역에서 V번째 역으로 이동하는 데 드는 비용의 최솟값을 구하자.

정기권 timer 2s memory 256MB

정기권 2s 256MB