#include<iostream>using namespace std;#define MAX 9999int book[101],n,e[101][101],min=MAX;
//cur是当前所在的城市，dis是当前已经走过的路径void dfs(int cur,int dis){	int j;	if(dis>min) return;	if(cur==n)	{		if(dis<min) min=dis;		return;	}	for(j=1;j<=n;j++)	{if(e[cur][j]!=MAX&&book[j]==0)	{  		book[j]=1;		dfs(j,dis+e[cur][j]);		book[j]=0;	}	}	return;}int main(){	int i,j,m,a,b,c;	cin>>n>>m;	for(i=1;i<=n;i++)	{		for(j=1;j<=n;j++)		{			if(i==j) e[i][j]=0;			else e[i][j]=MAX;		}	}	for(i=1;i<=m;i++)	{		cin>>a>>b>>c;		e[a][b]=c;	}	book[1]=1;	dfs(1,0);	cout<<min;	return 0;}