문제
조이가 사는 도시에는 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번째 역으로 이동하는 데 드는 비용의 최솟값을 구하자.
입력
첫 번째 줄에 역의 개수를 나타내는 자연수 N과, 철도 노선의 개수를 나타내는 자연수 M이 주어진다.
두 번째 줄에 조이가 정기권을 사려는 두 역을 나타내는 자연수 S와 T가 주어진다.
세 번째 줄에 조이가 다니는 서점의 위치를 나타내는 두 개의 자연수 U와 V가 주어진다.
네 번째 줄부터 M개의 줄에 철도 노선의 정보가 주어진다. i번째 줄에는 3개의 자연수 A_i, B_i, C_i가 주어진다 (1 ≦ i ≦ M).
이것은 i번째 철도 노선이 A_i번째 역과 B_i번째 역을 양방향으로 연결하며, 그 운임이 C_i원임을 나타낸다.
[제한]
모든 입력 데이터는 다음을 만족한다.
• 2 ≦ N ≦ 100,000
• 1 ≦ M ≦ 200,000
• 1 ≦ S, T, U, V ≦ N
• S≠T, U≠V
• S≠U or T≠V
• 임의의 두 역은 한 개 이상의 철도 노선을 선택하여 이동할 수 있다.
• 1 ≦ A_i < B_i ≦ N (1 ≦ i ≦ M)
• 1 ≦ i < j ≦ M에 대하여 A_i ≠ A_j 또는, B_i ≠ B_j
• 1 ≦ C_i ≦ 1,000,000,000 (1 ≦ i ≦ M).
부분문제 1 [16 점]
• S = U
부분문제 2 [15 점]
• S번째 역과 T번째 역으로, 최소의 요금으로 이동할 때 가능한 경로는 1 가지 밖에 없다.
부분문제 3 [24 점]
• N ≦ 300
부분문제 4 [45 점]
• 추가 제한은 없다.
출력
정기권의 경로를 적절하게 선택했을 때, 역 U에서 역 V로 이동할 때 드는 비용의 최솟값을 의미하는 숫자 하나를 출력한다.
예제1
입력
66
16
14
121
231
351
243
452
561
출력
2
예제2
입력
65
12
36
121000000000
231000000000
341000000000
451000000000
561000000000
출력
3000000000
예제3
입력
88
57
68
122
233
344
141
155
266
377
488
출력
15
예제4
입력
55
15
23
121
2310
2410
3510
4510
출력
0
예제5
입력
1015
68
79
2712
81017
131
3814
5715
237
11014
3612
1510
891
297
141
181
247
5616
출력
19
힌트
출처
JOI 2018