E - TOURS13 (65)

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

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define trav(a, x)   for (auto& a: x)
#define pb        push_back
#define mp        make_pair
#define fus       first
#define sec       second

typedef pair<int, int>  pi;
typedef vector<int>     vi;
typedef vector<pi>      vpi;

template<typename T>inline void getSigned  (T& n) {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign(c=='-');if(sign)c=getchar();n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';if(sign)n=-n;}
inline int    readint()    { int x;    return getSigned(x), x; }
const int INF  = (1 << 30);
const int LOVE = 1411;

/// ================================ Main part ================================

void Dijkstra(int n, int i, vpi edge[]){
    vi d(n + 1, INF);
    priority_queue<pi, vpi, greater<pi>> pq;
    trav(j, edge[i]) pq.push(j), d[j.sec] = j.fus;
    while(!pq.empty()){
        int v = pq.top().sec,
            vlen = pq.top().fus;
        pq.pop();
        if(vlen != d[v]) continue;
        if(v == i){
            cout << vlen << '\n'; return;
        }
        trav(j, edge[v]){
            int u = j.sec,
                ulen = j.fus;
            if(vlen + ulen < d[u])
                pq.push(mp(d[u] = vlen + ulen, u));
        }
    }
    puts("-1"); return;
}

void query(){
    int n, m; cin >> n >> m;
    int u, v, c;
    vpi edge[n + 1];
    while(cin >> u >> v >> c, edge[u].pb(mp(c, v)), --m);
    FOR(i, 1, n + 1) Dijkstra(n, i, edge);
}

int main(){
    for(int t = readint(); t--;)
        query();
    return 0;
}