Shortest Shortest Path

The city where Seonno lives has (N) subway stations, numbered (1) through (N). The subway consists of (M) lines, and each line runs one-way between two different stations.

Seonno lives at station (x), and the company is at station (y). Tired of transferring, Seonno wants to commute along a shortest shortest path: a path to work that has the shortest distance and, at the same time, uses the fewest lines. That is, a shortest shortest path is a shortest path that also uses the smallest number of lines.

Given the subway lines, find the travel distance of a shortest shortest path to work, the number of lines it uses, and the number of distinct shortest shortest paths.

The first line gives (N), (M), (x), and (y), separated by spaces.

The next (M) lines give (u), (v), and (w), separated by spaces, describing one subway line each. This means there is a subway line from station (u) to station (v), and using it covers a distance of (w).

There can be multiple lines from one station to a particular station. In that case, those lines are all distinct lines.

If there is no path from (x) to (y),

• print "-1" on the first line.

If there is a path from (x) to (y),

• print on the first line the travel distance of a shortest shortest path from (x) to (y).
• print on the second line the number of subway lines used by a shortest shortest path from (x) to (y).
• print on the third line the number of distinct shortest shortest paths from (x) to (y), modulo (10^9+9). Two paths are considered distinct if they use different lines, even when the sequence of stations visited is the same.

• (2 \le N \le 100,000)
• (2 \le M \le 300,000)
• (1 \le x, y \le N), (x \ne y)
• (1 \le u, v \le N), (u \ne v)
• (1 \le w \le 200,000)
• Every line is one-way.

Suppose the subway lines are as follows, Seonno lives at station 1, and the company is at station 5. Then a shortest shortest path has travel distance 6, uses 2 lines, and there is 1 such path.