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 modeled 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