#include <bits/stdc++.h>
#define int long long
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int t,n,m,i,j,a,b,c,l,k;
int mat[200][200];
int dp[900006][20];
signed main()
{   f>>n>>m;
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            mat[i][j]=1e18;
        }
    }
    for (i=1;i<=m;i++){
        f>>a>>b>>c;
        mat[a][b]=min(mat[a][b],c);
    }
    for (i=0;i<n;i++){
        for (j=0;j<=(1<<(n));j++){
            dp[j][i]=1e18;
        }
    }
    dp[1][0]=0;
    for (i=1;i<=(1<<(n))-1;i+=2){
        for (j=1;j<n;j++){
            if (!(i&(1<<j))){
                for (k=0;k<n;k++){
                    if ((1<<(k))&(i))
                    dp[i+(1<<j)][j]=min(dp[i+(1<<j)][j],dp[i][k]+mat[k][j]);
                }
            }
        }
    }
    int mini=1e18;
    for (i=1;i<n;i++)
    mini=min(mini,dp[(1<<n)-1][i]+mat[i][0]);
    if (mini==1e18){
        g<<"Nu exista solutie\n";
    }
    g<<mini<<'\n';
    return 0;
}