#include <bits/stdc++.h>
#include <limits>
#define N 19
#define INF 100000001
#define ll long long
#define f first
#define s second
using namespace std;
ifstream in("hamilton.in");
ofstream out("hamilton.out");
int dp[1<<N][N], g[N][N], c[N][N], r[N][N], p[N];
int main(){
    int n,m,x,y,w,k,i,j,mx=INF;
    in>>n>>m;
    for(i=0; i<n; ++i)
        for(j=0; j<n; ++j)
            c[i][j]=INF;
    for(i=1; i<=m; ++i){
        in>>x>>y>>w;
        g[y][++p[y]]=x;
        c[x][y]=w;
    }
    for(i=0; i<(1<<n); ++i){
        for(j=0; j<n; ++j){
            r[i][j]=INF;
            if(i==1 && !j)
                r[1][0]=0;
            if(i&(1<<j))
                for(k=1; k<=p[j]; ++k)
                    if(i&(1<<g[j][k]))
                        r[i][j]=min(r[i][j], r[i^(1<<j)][g[j][k]]+c[g[j][k]][j]), cout<<i<<" "<<j<<" "<<g[j][k]<<": "<<r[i][j]<<"\n";
        }
    }
    for(i=1; i<=p[0]; ++i)
        mx=min(mx, r[(1<<n)-1][g[0][i]]+c[g[0][i]][0]);
    if(mx>=INF) out<<"Nu exista solutie";
    else out<<mx;
    return 0;
}