import java.io.*;
import java.util.*;
class Main{
    static int N = 1005;
    static int M = 10005;
    static int[] h = new int[N];
    static int[] adj = new int[M];
    static int[] ne = new int[M];
    static int[] w = new int[M];
    static int[][] dis = new int[N][2];// dis[i][0] s到i点的最短路  dis[i][1] s到i点的次短路
    static int[][] cnt = new int[N][2];// cnt[i][0] s到i点的最短路条数 cnt[i][1] s到i点的次短路条数
    static int p;
    static void add(int a, int b, int c){
        adj[p] = b; ne[p] = h[a]; w[p] = c; h[a] = p++;
    }
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static int n, m, s, t;
    static int INF = Integer.MAX_VALUE;
    public static void main(String[] args) throws Exception{
        int T = Integer.parseInt(reader.readLine());
        for(int i = 0; i < T; i++){
            String[] l1 = reader.readLine().split(" ");
            n = Integer.parseInt(l1[0]);
            m = Integer.parseInt(l1[1]);
            p = 0;
            Arrays.fill(h, -1);
            for(int j = 0; j < m; j++){
                String[] line = reader.readLine().split(" ");
                int a = Integer.parseInt(line[0]);
                int b = Integer.parseInt(line[1]);
                int c = Integer.parseInt(line[2]);
                add(a, b, c);
            }
            String[] l2 = reader.readLine().split(" ");
            s = Integer.parseInt(l2[0]);
            t = Integer.parseInt(l2[1]);
            System.out.println(dijkstra());
        }
    }
    public static int dijkstra(){
        for(int j = 0; j < N; j++) {
            Arrays.fill(dis[j], INF);
            Arrays.fill(cnt[j], 0);
        }
        dis[s][0] = 0; dis[s][1] = 0; cnt[s][0] = 1;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)->a[1]-b[1]);
        pq.offer(new int[]{s, 0});
        while(!pq.isEmpty()){
            int[] cur = pq.poll();
            int u = cur[0];
            int dist = cur[1];
            int k = -1; 
            //dist对应u的最短最短路时k=0， 次短路时k=1，否则说明之前dis[u]已找到更优路，dist为次次次次路
            if(dist == dis[u][0]) k = 0;
            else if(dist == dis[u][1]) k = 1;
            if(k == -1) continue; // dist轮到的时候，dis[u][]已经更新了，那么这个dist就没有意义了
            for(int i = h[u]; i != -1; i = ne[i]){
                int v = adj[i];
                int newDist =  dist + w[i];
                if(dis[v][0] > newDist){
                    // 0 表示最短路，1表示次短路
                    // 如果要更新最短路，那么意味着同时要更新次短路（原来的最短路变成了次短路）
                    dis[v][1] = dis[v][0];
                    cnt[v][1] = cnt[v][0];
                    dis[v][0] = newDist;
                    cnt[v][0] = cnt[u][k];
                    pq.offer(new int[]{v, newDist});
                }else if(dis[v][0] == newDist){
                    cnt[v][0] += cnt[u][k];
                }else if(dis[v][1] > newDist){
                    dis[v][1] = newDist;
                    cnt[v][1] = cnt[u][k];
                    pq.offer(new int[]{v, newDist});
                }else if(dis[v][1] == newDist){
                    cnt[v][1] += cnt[u][k];
                }
            }
        }
        if(dis[t][0] == dis[t][1] - 1) return cnt[t][0] + cnt[t][1];
        return cnt[t][0];
    }
}