#include <bits/stdc++.h>

using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int n,m,x,y,z;
struct Edge{int nod,cost;};
const int STARE_MAX = (1<<18)-1;
int dp[STARE_MAX][19];
vector<Edge> G[19];

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});
    }
    dp[1][0]=0;
    for(int i=1;i<(1<<n);i++) {
        for(int j=0;j<n;j++) {
            if(i&(1<<j)) {
                for(auto w:G[j]) {
                    if((i&(1<<w.nod))==0&&dp[i][j]!=INT_MAX)
                        dp[i|(1<<w.nod)][w.nod]=min(dp[i|(1<<w.nod)][w.nod],dp[i][j]+w.cost);
                }
            }
        }
    }
    int best = INT_MAX;
    for(int i=1;i<n;i++) if(dp[(1<<n)-1][i]!=INT_MAX) {
        for(auto w:G[i]) if(w.nod==0) {
            best=min(best,dp[(1<<n)-1][i]+w.cost);
        }
    }
    if(best==INT_MAX) fout<<"Nu exista solutie";
    else fout<<best;
    return 0;
}