Given a bidirectional weighted graph of ~N~ nodes and ~M~ edges, print the length of the shortest path from ~A~ to ~B~, 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, ~N, M, A, B~ ~(2 \le N \le 10^5, 1 \le M \le 2 \times 10^5, 1 \le A, B \le N, A \neq B)~.

The next ~M~ lines will each contain three integers, ~u, v, w~ ~(1 \le u, v \le N, 1 \le w \le 10^3)~. 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