드라이브

도시가 n개 있는 나라가 있다. 도시에는 1번부터 n번까지 번호가 붙어 있고, 일부 도시 쌍은 도로로 연결되어 있다. 당신은 현재 S번 도시에 있으며, 자동차를 몰고 T번 도시까지 가려고 한다.

각 도로에는 비용이 하나씩 정해져 있다. 드라이브를 시작한 뒤 첫 번째 도로를 지날 때에는 비용을 내지 않는다. 그 다음부터는 지금까지 지나온 도로 비용의 최솟값을 m, 최댓값을 M, 이번에 지나려는 도로의 비용을 x라고 하자.

• x < m이면 m - x만큼 추가로 지불한다.
• x > M이면 x - M만큼 추가로 지불한다.
• m <= x <= M이면 추가로 지불하지 않는다.

예를 들어 비용이 3, 1, 5, 4, 2, 7인 도로를 차례로 지나면 각 도로에서 내는 비용은 0, 2, 2, 0, 0, 2이고, 총 비용은 6이다.

도로 정보가 주어질 때, 총 지불 비용이 최소가 되는 드라이브 경로를 구하라.

첫째 줄에 네 정수 n, m, S, T가 주어진다. n은 도시의 개수이고 m은 도로의 개수이다.

• 3 <= n <= 500
• 1 <= m <= 2,000

다음 m개의 줄에는 도로 하나를 나타내는 세 정수 a, b, c가 주어진다. 이는 a번 도시와 b번 도시를 잇는 도로의 비용이 c라는 뜻이다.

• 1 <= c <= 1,000,000,000
• a와 b는 서로 다르다.
• 같은 두 도시를 직접 잇는 도로는 최대 하나뿐이다.

첫째 줄에 최소 총 지불 비용을 출력한다.

둘째 줄에는 선택한 드라이브 경로에서 방문하는 도시 번호를 순서대로 출력한다.

경로가 존재하지 않는 입력은 주어지지 않는다.