자재 운반

말라스트라나의 건물을 어린이집으로 개조하면서 많은 자재를 한 곳에서 다른 곳으로 옮겨야 한다. 시멘트, 모래, 철근처럼 튼튼한 짐도 있고 벤치, 창문, 컴퓨터처럼 깨지기 쉬운 짐도 있다. 짐의 종류에 맞는 차량을 골라야 하고, 요즘 경유값이 워낙 비싸서 차량이 지나는 경로도 가능한 한 짧아야 한다. 도로망이 아주 촘촘하지는 않지만 길을 파악하기가 꽤 까다로워서, 학부는 짐마다 운반 경로를 짜 주는 프로그램을 맡기기로 했다.

입력은 짐 하나에 해당하는 블록 여러 개로 이루어진다. 각 블록의 첫 줄에는 네 정수 N, M, S, C가 주어진다. N은 도로망의 주요 지점 개수(1 ≤ N ≤ 10,000), M은 지점 사이를 잇는 도로의 개수(M ≤ 50,000), S는 짐을 싣는 지점의 번호, C는 짐을 내릴 지점의 번호다. 지점에는 1번부터 N번까지 번호가 붙어 있다. 입력은 0이 네 개 적힌 줄로 끝나며, 이 줄은 처리하지 않는다.

블록의 첫 줄 다음에는 도로 하나를 설명하는 줄이 M개 이어진다. 각 줄에는 세 정수 A, B, V가 공백으로 구분되어 주어진다. A는 도로가 시작하는 지점, B는 도로가 끝나는 지점이고, 도로는 모두 일방통행이다. V는 이 도로로 자재를 옮길 때 드는 비용이다(1 ≤ V ≤ 1,000). S에서 C로 가는 경로는 항상 존재한다고 가정해도 된다.

각 블록마다 S에서 C까지 짐을 옮기는 데 드는 최소 비용을 한 줄에 하나씩 출력한다.