Drive

There is a country with n cities. The cities are numbered from 1 to n, and some pairs of cities are connected by roads. You are currently in city S and want to drive to city T.

Each road has a cost. After the drive begins, you pay nothing for the first road you use. For every later road, let m be the minimum road cost among the roads used so far, M be the maximum road cost among the roads used so far, and x be the cost of the road you are about to use.

• If x < m, you additionally pay m - x.
• If x > M, you additionally pay x - M.
• If m <= x <= M, you pay nothing extra.

For example, if you use roads with costs 3, 1, 5, 4, 2, 7 in that order, the payments for those roads are 0, 2, 2, 0, 0, 2, for a total payment of 6.

Given the road information, find a driving route whose total payment is minimum.

The first line contains four integers n, m, S, and T. Here, n is the number of cities and m is the number of roads.

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

Each of the next m lines contains three integers a, b, and c, describing one road. It means that the road connecting cities a and b has cost c.

• 1 <= c <= 1,000,000,000
• a and b are different.
• At most one road directly connects the same pair of cities.

On the first line, print the minimum total payment.

On the second line, print the city numbers visited by the chosen driving route, in order.

Inputs with no valid route are not given.