## CANDN - Charly And Nito

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^{4} ). 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 -1Output:

20 4 3

4 1 1

hide comments

nadstratosfer:
2019-12-03 09:22:37
Great problem. Plenty of headache with pen and paper to get the right solution, then some more trying to understand a weird bug that I finally had to circumvent without learning why it happens. Not much score for the work it cost me, but feels good to get past it. |

Added by: | Pablo Ariel Heiber |

Date: | 2010-08-13 |

Time limit: | 3.146s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: NODEJS OBJC PERL6 VB.NET |

Resource: | FCEyN UBA ICPC Selection 2007 |