Introduction - If you have any usage issues, please Google them yourself
input
The data is less than 10 groups, ensuring only one source and a sink. Input a number of vertices n (2<=n<=10000), the number of edges m (1<=m <=50000). Next, the M line is the input side, which is the edge starting point SV, the edge point EV, and the edge weight W (1<=sv, ev<=n, SV! = EV, 1<=w <=20). The data ensures that the graph is connected.
output
The weight of the key path and the path of the key path from the source point (if there are many, please output the smallest dictionary order)
sample input
9 1 1
1 2 6
1 3 4
1 4 5
2 5 1
3 5 1
4 6 2
5 7 9
5 8 7
6 8 4
8 9 4
7 9 2
sample output
18
12
25
57
79