14554번 - The Other Way

문제

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

출력

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

제한

힌트