#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 200 + 10, INF = 0x7ffffff;
int t, n, m;
int f[N][N];
void Floyd() {
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++) if(i != k)
            for(int j=1; j<=n; j++) if(i != j && j != k)
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}
int main() {
    freopen("hardest.in", "r", stdin);
    freopen("hardest.out", "w", stdout);
    scanf("%d", &t);
    int u, v, w;
    while(t--) {
        scanf("%d %d", &n, &m);
        for(int i=0; i<=n; i++) {
            fill_n(f[i], n+1, INF);
            f[i][i] = 0;
        }
        for(int i=0; i<m; i++) {
            scanf("%d %d %d", &u, &v, &w);
            f[u][v] = f[v][u] = min(f[u][v], w);
        }
        Floyd();
        printf("%d\n", f[1][n] == INF ? -1 : f[1][n]);
    }
    return 0;
}