学步园

#include <iostream>
using namespace std;

const int INF=999999;
int n,m,adj[250][250],vis[250],dis[250];
void dijkstra(int v)
{
	for(int i=0;i<n;i++)
	{
		dis[i]=adj[v][i];
		vis[i]=0;
	}
	vis[v]=1;
	for(int i=1;i<n;i++)
	{
		int min=INF,u=0;
		for(int j=0;j<n;j++)
		{
			if(!vis[j]&&dis[j]<min)
			{
				u=j;
				min=dis[j];
			}
		}
		vis[u]=1;
		for(int j=0;j<n;j++)
			if(!vis[j]&&dis[u]+adj[u][j]<dis[j])
				dis[j]=dis[u]+adj[u][j];
	}
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
				adj[i][j]=INF;
			adj[i][i]=0;
		}

		int a,b,c;
		while(m--)
		{
			cin>>a>>b>>c;
			if(c<adj[a-1][b-1])
				adj[a-1][b-1]=adj[b-1][a-1]=c;
		}
		dijkstra(0);
		if(dis[n-1]==INF) cout<<-1<<endl;
		else cout<<dis[n-1]<<endl;
	}
	return 0;
}