#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

constexpr int inf = 1E9;

void solve() {
    int n, m;
    std::cin >> n >> m;
    
    std::vector<int> dp(n, inf);
    dp[0] = 0;
    
    std::vector<int> u(m), v(m), t(m);
    for (int i = 0; i < m; i++) {
        std::cin >> u[i] >> v[i] >> t[i];
        u[i]--;
        v[i]--;
    }
    std::vector<int> ord(m);
    std::iota(ord.begin(), ord.end(), 0);
    std::sort(ord.begin(), ord.end(),
        [&](int i, int j) {
            return t[i] < t[j];
        });
    std::vector<std::array<int, 2>> upd;
    for (int l = 0, r = 0; l < m; l = r) {
        while (r < m && t[ord[l]] == t[ord[r]]) {
            int i = ord[r++];
            upd.push_back({v[i], dp[u[i]]});
            upd.push_back({u[i], dp[v[i]] + 1});
        }
        for (auto [u, x] : upd) {
            dp[u] = std::min(dp[u], x);
        }
        upd.clear();
    }
    
    int ans = dp[n - 1];
    if (ans >= inf) {
        ans = -1;
    }
    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}