#include <bits/stdc++.h>
using namespace std;
#define INF (int)1e9
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int mx[22][22];
int dp[1<<18][22];
bool is_one(int msk,int bit) {
    return (msk&(1<<bit))!=0;
}
int set_bit(int msk,int bit) {
    return msk|(1<<bit);
}
int main() {
    int n,m;
    fin>>n>>m;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            mx[i][j]=INF;
        }
    }
    for (int i=0; i<(1<<18); i++) {
        for (int j=0; j<n; j++) {
            dp[i][j]=INF;
        }
    }
    for(int i=1; i<=m; i++) {
        int x,y,c;
        fin>>x>>y>>c;
        mx[x][y]=c;
    }
    dp[1][0]=0;
    for(int msk=0; msk<(1<<18); msk++) {
        for(int nod1=0; nod1<n; nod1++) {
            if(!is_one(msk,nod1)) {
                continue;
            }
            for (int nod2=0; nod2<n; nod2++) {
                if(is_one(msk,nod2)||nod1==nod2) {
                    continue;
                }
                int msk2=set_bit(msk,nod2);
                dp[msk2][nod2]=min(dp[msk2][nod2],dp[msk][nod1]+mx[nod1][nod2]);
            }
        }
    }
    int ans=INF;
    for(int nod=0; nod<n; nod++) {
        ans=min(ans,dp[(1<<n)-1][nod]+mx[nod][0]);
    }
    if(ans==INF) {
        fout<<"Nu exista solutie";
    } else {
        fout<<ans;
    }
    return 0;
}