All Submissions


Given a graphical network of nodes and undirected and weighted edges.Akshit and Sunny start traversing the graph from the same starting point but they have different destinations.They both, being lazy, want to traverse the shortest possible path from the starting point to their respective destinations.Your task is to find the length of the path that they both traverse with each other and the length of the paths that both have to traverse alone.

INPUT
The first line of input contains the number of test cases T.
Each test case begins with two integers N and M, denoting the number of nodes and edges respectively.
Next M line will contain three integers N1, N2 and K,where N1 and N2 denote the node numbers which are directly connected by an edge and K denotes the length of the edge.
Last line of each test case will contain three integers S, A and B where S is the starting point,A is the destination of Akshit and B is the destination of Sunny.

OUTPUT
For each test case print three integers D, AD and SD separated by space,where D is the length of the path that they both traverse with each other,AD is the length of the path Akshit has to traverse alone and SD is the length of the path Sunny has to traverse alone.

CONSTRAINT

T <= 20
3 <= N <= 5000
2 <= M <= 10000
1 <= N1,N2,S,A,B <= N
1 <= K <= 10000


SAMPLE INPUT

2
5 4
3 4 10
4 5 10
5 1 3
5 2 4
3 2 1
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 7 8


SAMPLE OUTPUT

20 4 3
4 1 1


Problem Setter : Akshay Kumar
Problem Tester : Pushkar Anand


Languages: Brain,C,C++,Java,C#,JavaScript,Pascal,Perl,PHP,Python,Ruby,Text

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0