#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,b,e,ans = 2e9;
struct aa
{
    int v,cnt,c;
};
bool vis[200005];
vector<pair<int,int>>p[200005];
deque<aa>q;
map<pair<int,int>,bool>mp;
int bfs()
{
    while(!q.empty()) q.pop_front();
    q.push_back({b,0,0});
    while(!q.empty())
    {
        auto [v,cnt,c] = q.front();
        q.pop_front();
        if(v==e) {
            ans = min(ans,cnt);
            continue;
        }
        for(auto [u,cc]:p[v])
        {
            if(!mp[{u,cc}])
            {
                if(c == cc)
                    q.push_front({u,cnt,cc});
                else q.push_back({u,cnt+1,cc});
            }
            mp[{u,cc}] = 1;
        }
    }
    return ans;
}
void solve()
{
    cin>>n>>m;
    fill(vis,vis+n+1,false);
    mp.clear();
    for(int i=1;i<=n;i++)p[i].clear();
    for(int i=1;i<=m;i++)
    {
        int u,v,c;
        cin>>u>>v>>c;
        p[u].push_back({v,c});
        p[v].push_back({u,c});
    }
    ans = 2e9;
    cin>>b>>e;
    cout << bfs() << endl;
}
signed main()
{
    int t;cin>>t;
    while(t--)solve();
    return 0;
}

复杂度不知道假没假

wrong answer 361st numbers differ - expected: '1', found: '2'