#include <bits/stdc++.h>

using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int n,m,x,y,z;
const int STARE_MAX = (1<<18)-1;
int dp[STARE_MAX][18];
int cost[18][18];
int best = INT_MAX;

int main()
{
    fin>>n>>m;
    for(int i=0;i<(1<<n);i++) for(int j=0;j<n;j++) dp[i][j]=INT_MAX;
    for(int i=1;i<=m;i++) {
        fin>>x>>y>>z;
        cost[x][y]=z;
    }
    dp[1][0]=0;
    for(int i=1;i<(1<<n);i++) {
        for(int j=0;j<n;j++) {
            if(i&(1<<j)) {
                for(int w=0;w<n;w++) if(cost[j][w]){
                    if((i&(1<<w))==0&&dp[i][j]!=INT_MAX)
                        dp[i|(1<<w)][w]=min(dp[i|(1<<w)][w],dp[i][j]+cost[j][w]);
                }
            }
        }
    }

    for(int i=1;i<n;i++) if(dp[(1<<n)-1][i]!=INT_MAX&&cost[i][0]) {
        best=min(best,dp[(1<<n)-1][i]+cost[i][0]);
    }

    if(best==INT_MAX) fout<<"Nu exista solutie";
    else fout<<best;
    return 0;
}