관광 경로

여행사 Your Personal Holiday는 베네룩스 지역을 도는 버스 관광 상품을 운영한다. 버스는 매일 도시 S에서 출발해 다른 도시 F까지 이동하고, 승객은 달리는 동안 길가의 명소를 구경한다. 버스는 경치가 좋은 도시 몇 곳에 정차하기도 하는데(한 번도 서지 않을 수도 있다), 승객은 그곳에서 내려 동네 명소를 둘러본다.

관광객 무리마다 보고 싶은 명소가 다르고, 그래서 S에서 F까지 가는 경로의 선호도 갈린다. 그래서 Your Personal Holiday는 서로 다른 경로를 여러 개 제시하려고 한다. 다만 호텔을 미리 예약해 두었으므로 출발 도시 S와 도착 도시 F는 고정이다. S에서 F로 가는 두 경로는, 도시 A에서 도시 B로 가는 도로 중 한쪽 경로에만 들어 있는 도로가 하나라도 있으면 서로 다른 경로로 본다.

고를 수 있는 경로에는 제한이 하나 있다. 정차한 도시에서 관광할 시간을 충분히 남기고 연료도 아끼려면 버스는 S에서 F까지 짧은 경로로 가야 한다. 경로의 길이는 최단 거리이거나, 최단 거리보다 정확히 1만큼 긴 거리여야 한다. 최단 거리보다 1 긴 경로까지 허용하면 최단 경로만 고를 때보다 선택지가 늘어난다.

예를 들어 위 지도에서 S = 1, F = 5일 때 최단 경로는 1 → 2 → 5와 1 → 3 → 5 두 개이고, 길이는 모두 6이다. 길이가 1 더 긴 경로는 1 → 3 → 4 → 5 하나이며, 길이는 7이다.

베네룩스의 (일부) 도로 지도와 두 도시 S, F가 주어진다. 위 길이 제한을 만족하는 서로 다른 경로가 몇 개인지 구하라.

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

• 첫 줄에 도시의 수 $N$과 도로의 수 $M$이 공백 하나로 구분되어 주어진다. ($2 \le N \le 1000$, $1 \le M \le 10000$)
• 다음 $M$개의 줄에는 세 정수 $A$, $B$, $L$이 공백 하나로 구분되어 주어진다. 도시 $A$에서 도시 $B$로 가는 길이 $L$인 도로를 뜻한다. ($1 \le A, B \le N$, $A \ne B$, $1 \le L \le 1000$)
• 마지막 줄에 경로의 출발 도시 $S$와 도착 도시 $F$가 공백 하나로 구분되어 주어진다. ($1 \le S, F \le N$, $S \ne F$)

도로는 단방향이다. $A$에서 $B$로 가는 도로가 있다고 해서 $B$에서 $A$로 가는 도로가 반드시 있는 것은 아니다. 도시 $A$에서 도시 $B$로 가는 도로가 여러 개일 수도 있다.

$S$에서 $F$로 가는 경로는 적어도 하나 존재한다.

각 테스트 케이스마다 한 줄에 하나씩, 길이가 최단 거리이거나 최단 거리보다 정확히 1 긴 경로의 개수를 출력한다. 이 개수는 $10^9$ 이하임이 보장된다.

문제 설명의 그림은 첫 번째 예시에 들어 있는 두 테스트 케이스 중 첫 번째 지도이다.