키르는 마을가 $N$개 있는 나라에 살고 있다. 편의상 1번부터 $N$번 까지의 마을이라고 하자. 이들은 두 마을을 잇는 $M$개의 도로로, 양방향으로 연결되어 있다.</p>

키르는 $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$)

출력 형식

$S$에서 $E$까지 가는 최단 경로의 가짓수를 1000000009($10^9 + 9$)로 나눈 나머지를 구하여라.

예제 입력

3 4 1 3
1 2 1
2 1 1
2 3 1
1 3 2

예제 출력

3