#include <bits/stdc++.h>

using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int STARE_MAX = 1<<19;
const int NMAX = 19;
int n,m,x,y,z;
long best=LONG_MAX;
long dp[STARE_MAX][NMAX];
struct Edge{int nod,cost;};
struct Stare{int stare,nodCurent;long cost;};
vector<Edge> G[NMAX];
stack<Stare>S;

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;
        G[x].push_back({y,z});
    }
    S.push({1<<0,0,0});

    while(S.size()) {
        Stare top = S.top();
        S.pop();

        dp[top.stare][top.nodCurent]=top.cost;

        for(auto w:G[top.nodCurent]) {
            int nodVecin=w.nod;
            int costMuchie=w.cost;

            if(top.stare!=((1<<n)-1)&&
                dp[top.stare|(1<<nodVecin)][nodVecin]>dp[top.stare][top.nodCurent]+costMuchie)
                S.push({top.stare|(1<<nodVecin),nodVecin,dp[top.stare][top.nodCurent]+costMuchie});
        }
    }

    for(int i=1;i<n;i+=1) {
        for(auto x:G[i]) if(x.nod==0&&dp[(1<<n)-1][i]!=INT_MAX) {
                best=min(dp[(1<<n)-1][i]+x.cost,best);
        }
    }
    if(best==LONG_MAX)
        fout<<"Nu exista solutie";
    else fout<<best;
    return 0;
}