The Other Way

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.

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.

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.