#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int const INF=1e9;
int n, m, i, j, s, a, b, c;
int mat[20][20], vaz[20];
int dp[300005][20][2];

void dfs(int nod){
    for(i=0;i<n;i++){
        if(mat[nod][i]!=INF && !vaz[i]){
            vaz[i]=1;
            dfs(i);
        }
    }
}

int main()
{
    fin>>n>>m;

    for(i=1;i<=m;i++){
        fin>>a>>b>>c;
        mat[a][b]=c;
    }

    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            if(!mat[i][j])
                mat[i][j]=INF;
        }
    }

    dfs(0);
    for(i=0;i<n;i++){
        if(vaz[i]==0){
            fout<<"Nu exista solutie";
            return 0;
        }
    }


    for(s=1;s<=(1<<n)-1;s++){
        if(__builtin_popcount(s)==1){
            for(i=0;i<n;i++){
                dp[s][i][0]=INF;
                if((s&(1<<i))){
                    dp[s][i][0]=0;
                    dp[s][i][1]=i;
                }
            }
            continue;
        }
        for(i=0;i<n;i++){
            dp[s][i][0]=INF;
            if((s&(1<<i))){
                for(j=0;j<n;j++){
                    if(dp[s-(1<<i)][j][0]+mat[j][i]<dp[s][i][0]){
                        dp[s][i][0]=dp[s-(1<<i)][j][0]+mat[j][i];
                        dp[s][i][1]=dp[s-(1<<i)][j][1];
//                        cout<<j<<" "<<i<<" "<<dp[s][i][0]<<'\n';
                    }
                }
            }
        }
    }

    int MIN=INF;
    for(i=0;i<n;i++){
        int start=dp[(1<<n)-1][i][1];
        MIN=min(MIN, dp[(1<<n)-1][i][0]+mat[i][start]);
    }

    fout<<MIN;


    return 0;
}