#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define GET_SIZE(x) (((double)sizeof(x))/1024/1024)

using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int n,m;
int cost[20][20];
int dp[(1<<18)][20];

int main()
{
    cout<<GET_SIZE(dp);
    fin>>n>>m;
    for(int i=1;i<=m;i++) {
        int x,y,z;
        fin>>x>>y>>z;
        cost[x][y]=z;
    }
    memset(dp,INF,sizeof(dp));
    dp[1][0]=0;
    int stareFinala=(1<<(n))-1;
    for(int stare=1;stare<=stareFinala;stare++) {
        for(int i=0;i<n;i++) {
            if(stare&(1<<i)) {
                for(int j=0;j<n;j++) {
                    if(cost[i][j]&&!(stare&(1<<j))) {
                        dp[stare|(1<<j)][j]=min(dp[stare|(1<<j)][j],dp[stare][i]+cost[i][j]);
                    }
                }
            }
        }
    }
    int answer = INF;
    for(int i=1;i<n;i++) if(cost[i][0]) answer=min(answer,dp[stareFinala][i]+cost[i][0]);
    if(answer==INF) fout<<"Nu exista solutie";
    else fout<<answer;
    return 0;
}