Given a bidirectional weighted graph of nodes and edges, print the length of the shortest path from to , as well as the number of such shortest paths.
A shortest path is different from another shortest path if the edges of the path differ by at least one edge.
Input Specification
The first line will four integers, .
The next lines will each contain three integers, . It is guaranteed there are no self loops or duplicate edges. It is also guaranteed the entire graph is connected.
Output Specification
On the first line, output the length of the shortest path.
On the second line, output the number of such shortest paths.
Sample Input 1
4 5 1 3
1 2 1
2 3 2
3 4 2
2 4 1
1 3 3
Sample Output 1
3
2
Comments