JJ 랠리

이번 주말 도심은 매우 붐빈다. 자밧(Javad)과 잘랄(Jalal)은 각각 레이스를 주최하며, 이름은 JavadRally와 JalalRally이다. 두 사람은 각 레이스의 출발 교차로와 도착 교차로를 정했고, 지금은 각 레이스의 경로를 확정하려고 지역 경찰과 협의 중이다. 경찰은 레이스 당일 각 경로의 교차로를 통제하므로, 두 경로는 교차로를 하나도 공유하지 않는다. 또한 레이스 당일의 통제로 도심 교통 혼잡이 더해지므로, 각 경로는 출발지에서 도착지까지의 최단 경로여야 한다. 두 사람은 충돌 없는 경로를 찾는 데 어려움을 겪고 있어, 두 레이스를 조직하는 방법의 수를 세어 달라고 부탁했다. 두 레이스는 경로의 쌍이 다르면 다른 것으로 본다.

도시 지도에는 1번부터 $n$번까지 번호가 매겨진 교차로 $n$개와, 이들을 잇는 도로 $m$개가 있다. 각 도로에는 길이가 주어진다.

첫 줄에 정수 $n$ ($4 \le n \le 24$)과 $m$ ($1 \le m \le n(n-1)/2$)이 주어진다. 이어지는 $m$개의 줄은 도로를 나타내며, 정수 $u_i$ ($1 \le u_i \le n$), $v_i$ ($1 \le v_i \le n$), $w_i$ ($1 \le w_i \le 1000$)가 한 줄에 하나씩 주어진다. 각각 도로의 양 끝 교차로와 길이다. 자기 루프와 중복 간선은 없고, 모든 도로는 양방향이다. 마지막 줄에는 정수 $s_1$, $t_1$, $s_2$, $t_2$ ($1 \le s_1, t_1, s_2, t_2 \le n$)가 주어진다. 각각 Javad 경로의 출발 교차로와 도착 교차로, Jalal 경로의 출발 교차로와 도착 교차로이다. 네 수는 모두 서로 다르다. 주어진 지도는 연결되어 있어서, 임의의 두 교차로 사이에 경로가 존재한다.

두 레이스를 조직하는 서로 다른 방법의 수를 출력한다.