## A Path Problem 2

View as PDF

Points: 12
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

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