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

const int maxn = 1510000;

int n,m;
int tot;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int Tcase; cin>>Tcase;
    while(Tcase--)
    {
        vector< vector< pair<int,int> > >E;
        vector< vector<int> >V;
        vector< tuple<int,int,int> >ei;

        cin>>n>>m;
        V.resize(n+5);
        for(int i=1;i<=m;i++)
        {
            int x,y,t; cin>>x>>y>>t;
            ei.emplace_back(x,y,t);
            V[x].push_back(t),V[y].push_back(t);
            V[x].push_back(t+1),V[y].push_back(t+1);
        }
        
        tot=0;
        map< pair<int,int>,int>mp;
        for(int i=1;i<=n;i++)
        {
            sort(V[i].begin(),V[i].end());
            for(auto t:V[i])
            {
                auto temp= make_pair(i,t);
                if(mp.count(temp)==0) 
                {
                    mp[temp]=++tot;
            //        cerr<<i<<' '<<t<<' '<<tot<<endl;
                }
            }
        }
        E.resize(tot+5);
        for(int i=1;i<=n;i++)
        {
            int las=-1;
            for(auto t:V[i])
            {
                if(las!=-1 && las!=t)
                {
                    int u= mp[make_pair(i,las)], v=mp[make_pair(i,t)];
                    E[u].emplace_back(0,v);
                }
                las=t;
            }
        }
        for(auto [x,y,t]:ei)
        {
            E[ mp[make_pair(x,t)] ].emplace_back(0, mp[make_pair(y,t+1)] );
            E[ mp[make_pair(y,t)] ].emplace_back(1, mp[make_pair(x,t+1)] );
        }
        
        const int inf = 1e9;
        vector<int>dis(tot+5);
        for(int i=1;i<=tot;i++) dis[i]=inf;
        deque< pair<int,int> >q;
        dis[1]=0; q.push_back( make_pair(1,0) );
        while(!q.empty())
        {
            const auto [x,dx]=q.front(); q.pop_front();
            if(dx!=dis[x]) continue;
            for(auto [c,y]:E[x])
            {
                if(dis[y]>dx+c)
                {
                    dis[y]=dx+c;
                    if( c==0 ) q.push_front( make_pair(y,dis[y]) );
                    else q.push_back( make_pair(y,dis[y]) );
                }
            }
        }
        int ans=inf;
        for(auto t:V[n])
        {
            int u= mp[make_pair(n,t)];
            ans=min(ans,dis[u]);
        }
        if(ans==inf) ans=-1;
        cout<<ans<<'\n';
    }

    return 0;
}