Charly and Nito are friends and they like to be together at a nice bar in Palermo Hollywood. About at 3 a.m. they start to feel sleepy and want to go home. They want to get home quickly so each of them uses a path that minimizes the distance to his home. However, Charly and Nito also like to walk together while they talk about the “good old times”, so they want to walk together as much as possible.

Charly and Nito live in a city that can be modelled as a set of streets and junctions. Each street connects a pair of distinct junctions and can be walked in both directions. No two streets connect the same pair of junctions. Charly and Nito do not live together, and they do not live at the bar. There is at least one path from the bar to Charly’s home; the same occurs with Nito’s home.

Given information about the streets and junctions in the city, the locations of the bar, Charly’s home and Nito’s home, you must tell Charly and Nito the maximum distance that they can walk together without forcing them to walk more than the minimum distance from the bar to their respective homes. Charly and Nito also want to know how much each of them will walk alone.

Input

The input contains several test cases, each one described in several lines. The first line of each test case contains five integers J, B, C, N and S separated by single spaces. The value J is the number of junctions in the city (3 ≤ J ≤ 5000); each junction is identified by an integer number between 1 and J. The values B, C and N are the identifiers of the junctions where the bar, Charly’s home and Nito’s home are located, respectively (1 ≤ B, C, N ≤ J); these three junction identifiers are different. The value S is the number of streets in the city (2 ≤ S ≤ 150000). Each of the next S lines contains the description of a street. Each street is described using three integers E1, E2 and L separated by single spaces, where E1 and E2 identify two distinct junctions that are endpoints of the street (1 ≤ E1, E2 ≤ J), and L is the length of the street (1 ≤ L ≤ 10⁴). You may assume that each street has a different pair of endpoints, and that there exist paths from junction B to junctions C and N.

The last line of the input contains the number −1 five times separated by single spaces and should not be processed as a test case.

Output

For each test case output a single line with three integers T, C and N separated by single spaces, where T is the maximum distance that Charly and Nito can walk together, C is the distance that Charly walks alone, and N is the distance that Nito walks alone.

Example

Input:
5 3 2 1 6
3 4 10
4 5 10
5 1 3
5 2 4
1 3 23
2 3 24
8 1 7 8 8
1 2 1
2 4 1
2 3 1
4 5 1
3 5 1
5 6 1
6 8 1
6 7 1
-1 -1 -1 -1 -1

Output:
20 4 3
4 1 1