#include <bits/stdc++.h>

using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int mx[22][22];
int dp[1<<18][22];

bool CheckBit(int msk, int bit){ // este bitul 1?
    return (msk&(1<<bit))!=0;
}

int Add(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] = 1e9;
        }
    }
    for (int i=0;i<(1<<18);++i){
        for (int j=0;j<n;++j){
            dp[i][j] = 1e9;
        }
    }
    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 (!CheckBit(msk,nod1)) continue;
            for (int nod2=0;nod2<n;++nod2){
                if (CheckBit(msk,nod2) or nod1==nod2) continue;
                int msk2 = Add(msk,nod2);
                dp[msk2][nod2] = min(dp[msk2][nod2],dp[msk][nod1]+mx[nod1][nod2]);
            }
        }
    }
    int ans = 1e9;
    for (int nod=0;nod<n;nod++){
        ans = min(ans,dp[(1<<n)-1][nod]+mx[nod][0]);
    }
    if (ans==1e9){
        fout << "Nu exista solutie";
    }else{
        fout << ans;
    }
    return 0;
}