정올국에는 N개의 도시가 있고, M개의 양방향 도로가 이 도시들을 연결한다. 각 도로를 지날 때에는 일정한 시간이 걸린다. 어떠한 두 도시를 선택하더라도 그 두 도시를 직접 연결하는 도로는 최대 한 개다. 정올국에는 한 개의 고속도로가 있는데 이 고속도로는 두 종점 A와 B가 있고, 고속도로를 통하여 A에서 B로 가는 것이 가장 빠르다.

그런데 고속도로에는 사고가 자주 일어나기 때문에 사고에 의해 고속도로를 구성하고 있는 한 도로가 아예 폐쇄될 수 있다. 당신은 이런 경우를 고려하여 각 도로가 폐쇄되는 경우에 A에서 B로 갈 때 걸리는 최소 시간을 알아보고 싶다. 각 도로가 폐쇄되는 경우 A에서 B로 가는 최소 시간을 구하는 프로그램을 작성하여라.

입력

• 첫 번째 줄에는 도시의 수 N (1 ≤ N ≤ 2,000)과 도로의 수 M (1 ≤ M ≤ 100,000)과 고속도로의 두 종점의 번호 A, B (1 ≤ A, B ≤ N)가 주어진다.
• 두 번째 줄부터 M개의 줄에는 각 도로의 정보가 주어진다. 앞 두 수는 도로의 양 끝 도시의 번호이고 세 번째 수는 도로를 지날 때 걸리는 시간(≤ 100,000)이다.
• 마지막 줄에는 고속도로를 지나는 도시의 수 K와 고속도로를 지나는 도시의 번호가 주어진다. 고속도로를 지나는 도시의 번호는 A에서 시작해서 B로 끝나고, 고속도로는 A에서 B로 가는 최단경로 중 하나임이 보장된다.

출력

입출력 예

입력

5 6 1 5
1 2 1
2 3 3
2 5 100
3 4 3
3 5 5
4 5 3
4 1 2 3 5

출력

-1
101
10

번역: functionx
출처 : Balkan Olympiad in Informatics 2012, Day 1 Task 2
 http://boi2012.dms.rs/index.php?action=show&data=tasks