The Other Way

Time limit2sMemory limit256 MB

Summary

Count the number of distinct shortest paths between two towns in a weighted undirected multigraph, modulo 10^9+9.

Level: Medium5 of 10
Topics: Graph, Shortest path, Dynamic programming
Solved: No attempts yet

Problem

Kir lives in a country with $N$ towns, numbered 1 through $N$ . The towns are joined by $M$ roads, and every road can be walked in both directions.

Kir wants to go from town $S$ to town $E$ . He has always taken the same route, so he now wants to walk a different one, and he wonders how many different shortest routes from town $S$ to town $E$ there are. Two routes are different when one of them uses a road that the other does not. Roads are counted one by one, so if several roads join the same pair of towns, which road you take changes the route.

A shortest route is one whose total road length is as small as possible.

Answer Kir's question.

Input

The first line contains $N$ , $M$ , $S$ , and $E$ , separated by single spaces. ( $2 \le N \le 100000$ , $N-1 \le M \le 300000$ , $1 \le S, E \le N$ , $S \neq E$ )

Each of the next $M$ lines describes one road with $A$ , $B$ , and $C$ , separated by single spaces. It means a road of length $C$ joins town $A$ and town $B$ in both directions. ( $1 \le A, B \le N$ , $1 \le C \le 1000000000$ )

Several roads may join the same pair of towns, and a road with $A = B$ may appear.

Output

Print the number of shortest routes from town $S$ to town $E$ , modulo 1000000009 ( $10^9 + 9$ ). If no route from town $S$ to town $E$ exists, print 0.

Examples2

Example 1
Input
```
3 4 1 3
1 2 1
2 1 1
2 3 1
1 3 2
```
Expected output
```
3
```
Example 2
Input
```
4 3 1 4
1 2 5
1 2 7
3 4 2
```
Expected output
```
0
```