#include <bits/stdc++.h>
using namespace std;

#define ll long long
const ll inf = 1e18 + 10;
ll max(ll x, ll y) { return x > y ? x : y; }
ll min(ll x, ll y) { return x < y ? x : y; }

#define f(i, m, n) for (ll i = (ll)m; i < (ll)n; i++)
#define f_(i, n, m) for (ll i = (ll)n; i >= (ll)m; i--)
#define fa(i, x) for (auto i : x)
#define vll vector<ll>
#define vvll vector<vll>
#define vvvll vector<vvll>
#define pll pair<ll, ll>
#define vpll vector<pll>
#define vvpll vector<vpll>
#define ff first
#define ss second
#define pb push_back
#define nl cout << "\n";

deque<tuple<ll, ll, ll>> dq;
ll n, m;
ll s, e;
map<pll, ll> dist;
void solve()
{
    //CODE HERE
    dist.clear();
    cin >> n >> m;
    vvpll adj(n + 1);
    f(i, 0, m)
    {
        ll u, v, c;
        cin >> u >> v >> c;
        adj[u].pb({v, c});
        adj[v].pb({u, c});
    }

    cin >> s >> e;

    dq.push_back({0, s, 0});
    while (!dq.empty())
    {
        auto [dd, node, clr] = dq.front();
        dq.pop_front();
        if (node == e)
        {
            cout << dd << " ";
            break;
        }
        dist[{node, clr}] = dd;
        fa(&nbr, adj[node])
        {
            if (!dist.count({nbr.ff, nbr.ss}))
            {
                if (clr != nbr.ss)
                    dq.push_back({dd + 1, nbr.ff, nbr.ss});
                else
                    dq.push_front({dd, nbr.ff, nbr.ss});
            }
        }
    }

    dq.clear();
    nl
}
signed main()
{

    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    srand(chrono::high_resolution_clock::now().time_since_epoch().count());
    ll no_of_testcases = 1;
    cin >> no_of_testcases;
    f(curr_testcase, 1, no_of_testcases + 1)
    {
        solve();
    }
}