#include<bits/stdc++.h>
using namespace std;
const int N=1919810,mod=998244353;
typedef long long ll;
typedef pair<ll,ll> PII;
ll n,m,k;
ll a[N],b[N];
char s[N];

typedef struct{
    int to,val,w;
}Node;

vector<Node> e[N];
int q[N];

map<PII,ll> mp;


void __(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) e[i].clear();
    mp.clear();
    deque<PII> q;
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        e[u].push_back({v,w,0});
        e[v].push_back({u,w,1});
    }
    mp[{1,-1}]=0;
    q.push_back({1,-1});
    while(q.size()){
        PII t=q.front();
        // cout<<t.first<<" "<<t.second<<" "<<mp[t]<<endl;
        q.pop_front();
        for(auto [to,val,w]:e[t.first]){
            if(val<=t.second) continue;
            if(w==0){
                PII tt={to,val};
                if(mp.count(tt)) continue;
                mp[tt]=mp[t];
                q.push_front(tt);
            }else{
                PII tt={to,val};
                if(mp.count(tt)) continue;
                mp[tt]=mp[t]+1;
                q.push_back(tt);
            }
        }
    }
    ll ans=1e18;
    for(auto [u,v]:mp){
        if(u.first==n) ans=min(v,ans);
    }
    if(ans>1e10) puts("-1");
    else printf("%lld\n",ans);

}


int main(){
    int _;
    cin>>_;
    while(_--){
        __();
    }
}