#include <stdio.h>
int i,j,e[101][101],sum=0,book[101],n,s[10001]={0},a,b,min=999999;
void dfs(int cur)
{
printf("%d ",sum);
if (cur==n)
{
if(sum<min)
{
min=sum;
}
return;
}
for(i=1;i<=n;i++)
{
if(e[cur][i]!=999999&&book[i]==0)
{
book[i]=1;
sum=sum+e[cur][i];
dfs(i);
sum=sum-e[cur][i];
book[i]=0;
}
}
return;
}
int main()
{
int m;
scanf("%d %d",&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]=999999;
}
}
for(i=1;i<=m;i++)
{
scanf("%d %d",&a,&b);
scanf("%d",&e[a][b]);
}
book[1]=1;
dfs(1);
printf("%d",min);
return 0;
}