Hauling material

A building in Mala Strana is being converted into a nursery, and a lot of material has to move from one place to another. Some of it is sturdy, like cement, sand, or steel rods. Some of it is fragile, like benches, windows, or computers. The kind of load decides which truck is right for the job, and because diesel costs so much these days, the truck should also drive the shortest route it can. The road network is not especially dense, but finding your way around it is complicated enough that the faculty decided to commission a program that plans the route for each load.

The input has several blocks, one per load. Each block starts with a line holding four numbers N, M, S, and C. N is the number of significant places in the road network (1 ≤ N ≤ 10,000), M is the number of roads running between those places (M ≤ 50,000), S is the number of the place the load is carried from, and C is the number of the place it must reach. Places are numbered from 1 to N. The input ends with a line containing four zeros, and you do not process that line.

The first line of a block is followed by M lines describing the individual roads. Each of them holds three integers A, B, and V separated by spaces. A is the place a road leads from, B is the place it leads to, and every road is one way. V is the cost of moving the material along that road (1 ≤ V ≤ 1,000). You may assume a route from S to C always exists.

For each block, print one line with the minimum cost of moving the load from place S to place C.