#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("hamilton.in");
ofstream cout("hamilton.out");
int a[20][20];
int n,p;
int mi=20000000;
vector<vector<int>>m(20);
vector<vector<int>> dp((1<<18)+1,vector<int>(20,20000000));
bool ok(int stare, int x) {
    return !((stare>>x)&1);
}
void fct(int i,int stare) {
    for (auto x:m[i]) {
        int kstare=stare|(1<<x);
        if (x==0&&stare==(1<<n)-1)mi=min(mi,dp[stare][i]+a[i][x]);
        if (ok(stare,x)) {
            dp[kstare][x]=min(dp[kstare][x],dp[stare][i]+a[i][x]);
            //cout<<"sunt in starea "<<(stare|(1<<x))<<" se termina in "<<x<<" are val "<<dp[stare|(1<<x)][x]<<endl;
            fct(x,kstare);
        }
    }
}
int main() {
    cin>>n>>p;
    for (int i=0;i<p;i++) {
        int x,y,c;
        cin>>x>>y>>c;
        a[x][y]=c;
        m[x].push_back(y);
    }
    dp[1][0]=0;
    for (int i=1;i<(1<<n);i+=2) {
        for(int j=0;j<n;j++) {
            if (((i>>j)&1)==1) {
                for (auto x:m[j]) {
                    if (i==(1<<n)-1&&x==0) {
                        mi=min(mi,dp[i][j]+a[j][0]);
                    }
                    if (ok(i,x))dp[i|(1<<x)][x]=min(dp[i|(1<<x)][x],dp[i][j]+a[j][x]);

                }
                //cout<<"sunt in starea "<<i<<" se termina in "<<j<<" are val "<<dp[i][j]<<endl;
            }

        }
    }
    if (mi!=20000000)cout<<mi;
    else cout<<"Nu exista solutie";
}