#include
using namespace std;
const int INF=99999999;
int n,m;
int v[10000];//用来判断是否走过该点
int dist[10000][10000]; //第i和城市到第j个城市的距离
int minn=INF;
void dfs(int cur,int dis) //此处的dis是累计的最短距离
{
if(cur==n)
{
minn=min(minn,dis);
return ;
}
if(dis>minn)//说明这个地方是孤立点 不存在通道
return;
for(int j=1;j<=n;j++)
{
if(dist[cur][j]!=INF&&v[j]==0) //cur到城市j的距离不是无穷
{
v[j]=1;
dfs(j,dis+dist[cur][j]);
v[j]=0;
}
}
return;
}
int main()
{
int a,b,c;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==j) dist[i][i]=0;//自身距离是0 ,任意两孤立点之间是无穷
else
{
dist[i][j]=INF;
}
}
}
for( int i=1;i<=m;i++)
{
cin>>a>>b>>c;
dist[a][b]=c;//两个城市a b之间的距离是c
}
v[1]=1;
dfs(1,0);
cout<<minn;
return 0;
}