#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,best;
int dp[STARE_MAX][NMAX];
queue<int> Q;
struct Edge{int nod,cost;};
vector<Edge> G[NMAX];

void f(int stare, int nodCurent, int cost) {
    dp[stare][nodCurent]=cost;

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

        if(stare!=((1<<n)-1)&&
           dp[stare|(1<<nodVecin)][nodVecin]>dp[stare][nodCurent]+costMuchie)
            f(stare|(1<<nodVecin),nodVecin,dp[stare][nodCurent]+costMuchie);
    }
}

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});
    }
    f(1<<0,0,0);
    best=INT_MAX;
    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==INT_MAX)
        fout<<"Nu exista solutie";
    else fout<<best;
    return 0;
}