시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 3 3 3 100.000%

문제

n(3≤n≤500)개의 도시로 이루어진 나라가 있다. 이들 중 몇 개의 도시들은 서로 도로로 연결되어 있다. 당신은 당신의 취미 생활인 자동차 드라이브를 즐기려고 한다. 각각의 도시는 1, 2, 3, …, N의 번호가 붙어 있고, 현재 당신은 S번 도시에 위치하고 있다. 당신은 T번 도시로 가려고 한다.

각각의 도로를 지날 때에는 특정한 비용을 지불하여야 한다. 드라이브를 시작하면 처음으로 도로를 지날 때에는, 0원을 지불한다. 그 외의 경우에는 다음과 같은 방법을 이용하여 지불 비용을 계산한다. 우선, 현재까지 지난 도로들 중에서 최소인 비용을 m, 최대인 비용을 M이고, 현재 지나려는 도로의 비용이 x라고 하자. 만약 x가 m보다 작다면 m-x만큼의 비용을 추가로 지불하여야 한다. 만약 x가 M보다 크다면, x-M의 비용을 추가로 지불하여야 한다.

예를 들어, 비용이 3, 1, 5, 4, 2, 7인 도로들을 차례로 지났다고 하자. 그러면 각각을 지날 때 지불하는 비용은 0, 2, 2, 0, 0, 2가 되어, 총 6의 비용을 지불하게 된다.

도로에 대한 정보가 주어졌을 때, 지불하게 되는 총 비용을 최소로 하는 드라이브 경로를 찾는 것이 목적이다.

입력

첫째 줄에 네 정수 n, m(1≤m≤2,000), S, T가 주어진다. m은 도로의 개수를 나타낸다. 다음 m개의 줄에는 도로에 대한 정보를 나타내는 세 정수 a, b, c가 주어진다. 이는 a번 도시와 b번 도시를 연결하는 도로의 비용이 c(1≤c≤1,000,000,000)임을 나타낸다. a와 b는 항상 다르고, 두 도시는 오직 한 개의 도로(경로가 아님)로만 연결되어 있다.

출력

첫째 줄에 지불하는 비용을 출력한다. 다음 줄에는 방문하는 도시들을 차례로 출력한다. 답이 없는 경우는 입력으로 주어지지 않는다고 가정하자.

예제 입력

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

예제 출력

2
1 4 5 6

힌트