#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], low=1<<30;

struct edge{
    int v, c;
    edge(int x, int y){
        v=x, c=y;
    }
};
vector<edge> G[MAXN];

int check(int a, int b){
    for(auto p : G[a])
        if(p.v == b)
            return p.c;
    return 0;
}

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

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

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