#include <bits/stdc++.h>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
#define MAXN 19
#define pb push_back
int n, m, ciclu[MAXN], G2[MAXN][MAXN], low=1<<30;
vector<int> G[MAXN];

int valid(){
    int i, c=0, k;
    for(i=1;i<n;++i){
        k=G2[ciclu[i-1]][ciclu[i]];
        if(k==0)
            return 0;
        else
            c+=k;
    }
    k=G2[ciclu[n-1]][ciclu[0]];
        if(k)
    return c+k;
    return 0;
}

void solve(){
    do{
        int k=valid();
        if(k)
            low=min(low, k);
    }while(next_permutation(ciclu,ciclu+n-1));
}

int main()
{
    int x, y, z, i=0;
    fin>>n>>m;
    while(m--){
        fin>>x>>y>>z;
        G[x].pb(y);
        G2[x][y]=z;
    }
    for(i=0;i<n;++i)
        ciclu[i]=i;
    solve();
    low==(1<<30)?fout<<"Nu exista solutie":fout<<low;
	return 0;
}