1，2，5，6，7，8

#include<bits/stdc++.h>
using namespace std;
const int N=1510;
struct Edge
{
	int v,w;
};
int n,m,dp[N],flag,vis[N];
vector<Edge>e[N];
void dfs(int u,int sum)
{
	if(dp[u]>=sum) return;
	dp[u]=sum;
	if(u==n)
	{
		flag=1;
		return;
	}
	for(Edge i:e[u])
	{
		int v=i.v,w=i.w;
		if(vis[v]) return;
		vis[v]=1;
		dfs(v,sum+w);
		vis[v]=0;
	}
}
int main()
{
	memset(dp,~0x3f3f3f3f,sizeof dp);
	cin>>n>>m;
	while(m--)
	{
		int u,v,w;
		cin>>u>>v>>w;
		e[u].emplace_back(Edge{v,w});
		e[v].emplace_back(Edge{u,w});
	}
	vis[1]=1; 
	dfs(1,0);
	if(!flag) cout<<-1;
	else cout<<dp[n];
	return 0;
}