作者：姜博惟
时间：2016年8月28日11:57:35
************************************************/
#include<stdio.h>
#define MAX 9999999
int map[10001][10001] , book[10001][10001] ;
int M , N ;
int length = MAX;
void F(int place , int dis)
{
int i;
if(place > length) return ;
if(place == N)
{
if(dis < length)
{
length = dis;
}
return ;
}
for(i = 1 ; i <= N ; i++)
{
if(map[place][i] != MAX && book[place][i] == 0)
{
book[place][i] = 1;
F(i , dis + map[place][i]);
book[place][i] = 0;
}
}
return ;
}
int main()
{
int i , j , t1 , t2 , t3;
scanf("%d%d" , &N , &M);
for(i = 1 ; i <= N ; i++)
{
for(j = 1 ; j <= N ; j++)
{
if(i == j) map[i][j] = 0;
else map[i][j] = MAX;
}
}
for(i = 1 ; i <= M ; i++)
{
scanf("%d%d%d" , &t1 , &t2 , &t3);
map[t1][t2] = t3;
map[t2][t1] = t3;
}
book[1][1] = 1;
F(1 , 0);
printf("%d",length);
return 0;
}