#include <fstream>
#include <cstring>
#include <algorithm>

using namespace std;

#define Maxn 300

ifstream fin("hardest.in");
ofstream fout("hardest.out");

int n, m, i, j, k;
int a, b, c;
int map[Maxn][Maxn];

void search()
{
	memset(map,-1,sizeof(map));
	
	fin>>n>>m;
	
	for(a=1;a<=m;a++)
	{
		fin>>i>>j>>k;
		if(map[i][j]==-1||map[i][j]>k)
		{
			map[i][j]=map[j][i]=k;
		}
	}
	for(c=1;c<=n;c++)
    {
        for(a=1;a<=n;a++)
        {
            for(b=1;b<=n;b++)
            {
                if(a!=b && a!=c &&b!=c)
                {
                    if(map[a][c]!=-1 && map[c][b]!=-1)
                    {
						if(map[a][b]==-1 || map[a][b]>map[a][c]+map[c][b])
						{
                            map[a][b]=map[a][c]+map[c][b];
						}
					}
				}
			}
		}
	}
	if(n==1)
	{
		fout<<'0'<<endl;
	}
	else fout<<map[1][n]<<endl;
}
int main()
{
	int t, temp;
	
	fin>>t;
	
	for(temp=1;temp<=t;temp++)
	{
		search();
	}
	
	fin.close();
	fout.close();
	
	return 0;
}