Special Shortest Walk

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
You are given an undirected graph, you need to find the shortest walk in the graph from source to sink which satisfies the following property:
Let the shortest walk from source to sink be through edges E_{1} > E_{2} > ... > E_{k}, then Weight(E_{1}) > Weight(E_{2}) < Weight(E_{3}) > Weight(E_{4}) .....and so on.
Formally, the difference between adjacent edge weights in shortest walk should keep on switching from positive to negative and from negative to positive. And the first difference should be positive.
Input Format
First Line contains T, the number of Test cases.
First line of each test case contains N the number of nodes and M the number of edges.
Next M lines follows, each line contains 3 integers X, Y and Z, which denotes that there is an edge from X to Y with weight Z.
Next line contains 2 integer source and sink.
Output Format
For each test case, print the shortest walk satisfying the property. If no such walk exists then print "No Solution".
Constraints
1 ≤ Sum of N over all test cases ≤ 100000 1 ≤ Sum of M over all test cases ≤ 500000 3 ≤ N ≤ 100000 2 ≤ M ≤ 500000 1 ≤ T ≤ 2000 1 ≤ Z ≤ 100000000 1 ≤ X,Y ≤ N X != Y source != sink and there are no multi edges. source and sink will not be connected by a direct edgeSample Input
3 5 6 4 2 8 1 4 6 2 3 10 3 1 10 1 2 3 3 5 3 4 3 4 3 1 4 4 2 4 5 2 3 6 4 3 5 5 1 2 100 2 3 80 3 4 90 4 2 85 2 5 120 1 5Sample Output
19 No Solution 475Explanation
For First Test Case: Shortest Valid Walk: 4>1>2>3 For Second Test Case: There is no valid Walk satisfying the constraints.
Warning: Large Input files, some files are upto 10 MB
Author:  devuy11 
Tester:  anudeep2011 
Editorial  http://discuss.codechef.com/problems/SPSHORT 
Tags  cook55, devuy11, dijkstra, graph, mediumhard, pathsingraph, shortestpath 
Date Added:  11112014 
Time Limit:  8 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 