다른 길

키르가 사는 나라에는 마을이 $N$개 있고, 1번부터 $N$번까지 번호가 붙어 있다. 마을 사이에는 도로가 $M$개 놓여 있으며, 모든 도로는 양방향으로 다닐 수 있다.

키르는 $S$번 마을에서 $E$번 마을까지 가려고 한다. 늘 같은 길로만 다니던 키르는 다른 길도 걸어 보고 싶어서, $S$번 마을에서 $E$번 마을까지 가는 최단 경로가 서로 다른 것으로 몇 개나 되는지 궁금해졌다. 두 경로는 한쪽에서 지난 도로를 다른 쪽에서 지나지 않았을 때 서로 다르다. 도로는 한 개씩 구별하므로, 같은 두 마을을 잇는 도로가 여러 개 있으면 그중 어느 도로를 지났는지에 따라 경로가 달라진다.

최단 경로는 지나는 도로의 길이를 모두 더한 값이 가장 작은 경로를 말한다.

키르의 궁금증을 풀어 주자.

첫째 줄에 $N$, $M$, $S$, $E$가 공백 하나로 구분되어 주어진다. ($2 \le N \le 100000$, $N-1 \le M \le 300000$, $1 \le S, E \le N$, $S \neq E$)

다음 $M$개의 줄에 도로의 정보가 한 줄에 하나씩, $A$, $B$, $C$가 공백 하나로 구분되어 주어진다. $A$번 마을과 $B$번 마을을 길이 $C$의 도로가 양방향으로 잇는다는 뜻이다. ($1 \le A, B \le N$, $1 \le C \le 1000000000$)

같은 두 마을을 잇는 도로가 여러 개 주어질 수 있고, $A = B$인 도로도 주어질 수 있다.

$S$번 마을에서 $E$번 마을까지 가는 최단 경로의 개수를 1000000009($10^9 + 9$)로 나눈 나머지를 출력한다. $S$번 마을에서 $E$번 마을로 가는 경로가 하나도 없으면 0을 출력한다.