조이가 사는 도시에는 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로 이동할 때 드는 비용의 최솟값을 의미하는 숫자 하나를 출력한다.

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

6 5
1 2
3 6
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000

3000000000

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

5 5
1 5
2 3
1 2 1
2 3 10
2 4 10
3 5 10
4 5 10

0

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

첫 번째 예제에서는, 정기권을 살 때 사용할 수 있는 경로는 1→2→3→5→6만 가능하다. 1번째 역에서 4번째 역으로 이동할 때 소요되는 비용을 최소화하려면 1→2→3→5→4를 선택해야 하며, 비용은 아래와 같이 계산하여 2원이다. • 4번째 역과 5번째 역을 연결하는 철도 노선에서는 2원 • 나머지 철도 노선에서는 0원 2번째 예제에서는 3번째 역에서 6번째 역으로 이동하는 정기권을 사용한다.