문제
조이가 사는 도시에는 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
입력
6 6
1 6
1 4
1 2 1
2 3 1
3 5 1
2 4 3
4 5 2
5 6 1
출력
2
예제2
입력
6 5
1 2
3 6
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
출력
3000000000
예제3
입력
8 8
5 7
6 8
1 2 2
2 3 3
3 4 4
1 4 1
1 5 5
2 6 6
3 7 7
4 8 8
출력
15
예제4
입력
5 5
1 5
2 3
1 2 1
2 3 10
2 4 10
3 5 10
4 5 10
출력
0
예제5
입력
10 15
6 8
7 9
2 7 12
8 10 17
1 3 1
3 8 14
5 7 15
2 3 7
1 10 14
3 6 12
1 5 10
8 9 1
2 9 7
1 4 1
1 8 1
2 4 7
5 6 16
출력
19
힌트
출처
JOI 2018