#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e3 + 2;
bool vis[N];
int d[N], cnt[N], dx[N], cntx[N];
signed main () {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        vector <pair<int, int>> edge[N];
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
        int n, m, s, f;
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            d[i] = 0x3f3f3f3f3f3f3f3f;
            dx[i] = 0x3f3f3f3f3f3f3f3f;
        }
        memset (cnt, 0, sizeof(cnt));
        memset (cntx, 0, sizeof(cntx));
        memset (vis, 0, sizeof(vis));
        for (int i = 1; i <= m; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            edge[u].push_back({v, w});   
        }
        cin >> s >> f;
        d[s] = 0;
        q.push({d[s], s});
        cnt[s] = 1;
        while (!q.empty()) {
            auto u = q.top().second;
            q.pop();
            if (vis[u]) continue;
            vis[u] = 1;
            for (auto [v, w] : edge[u]) {
                if (d[v] > d[u] + w) {
                    dx[v] = d[v];
                    cntx[v] = cnt[v];
                    d[v] = d[u] + w;
                    cnt[v] = cnt[u];
                    q.push({d[v], v});
                    q.push({dx[v], v});
                }
                else if (d[v] == d[u] + w) {
                    cnt[v] += cnt[u];
                }
                if (d[v] < d[u] + w) {
                    if (d[u] + w < dx[v]) {
                        dx[v] = d[u] + w;
                        cntx[v] = cnt[u];
                        q.push({dx[v], v});
                    }
                    else if (dx[v] > dx[u] + w) {
                        dx[v] = dx[u] + w;
                        cntx[v] = cntx[u];
                        q.push({dx[v], v});
                    }
                    else if (dx[v] == dx[u] + w) {
                        cntx[v] += cntx[u];
                    }
                }
            }
        }
        int ans = 0;
        ans += cnt[f];
        if (dx[f] - d[f] == 1) ans += cntx[f];
        cout << ans << endl;
    } 
    return 0;
}