#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;

const int maxn = 200+5;
const int maxm = 10000;
const int inf = ~0U >> 2;

int T, n, m, u, v, w, map[maxn][maxn], dis[maxn];

void spfa()
{
    queue<int> q;   q.push(1);
    bool vis[maxn]; memset(vis, 0, sizeof(vis)); dis[1] = 0;
    while(!q.empty()) {
        int x = q.front(); q.pop();
        vis[x] = true;
        for(int i = 1; i <= n; i++) if(map[x][i] > 0 && dis[x]+map[x][i] < dis[i])
        {
            dis[i] = dis[x]+map[x][i];
            if(vis[i]) { vis[i] = false; q.push(i); }
        }
    }
}

int main()
{
    freopen("hardest.in", "r", stdin);
    freopen("hardest.out", "w", stdout);
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &m);
        memset(map, -1, sizeof(map));
       // memset(dis, 0xffffff, sizeof(dis));
        for(int i = 1; i <= n; i++) dis[i] = inf;
        for(int i = 1; i <= m; i++) {
            scanf("%d%d%d", &u, &v, &w);
            map[u][v] = map[v][u] = w;
            spfa();
            printf("%d\n", (dis[n] == inf ? -1: dis[n]));
        }
    }
    return 0;
}