#include <fstream>
#include <cstdio>
#include <vector>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int n,m,viz[20],x,y,z,perm[20],adi[20][20],cost=1e9;
bool ok;
vector<pair<int,int>>v[20];
void bkt( int k, int pret){
     if(k==n){
                if(adi[perm[n-1]][perm[0]]){
                    ok=1;
                    cost=min(cost,pret+adi[perm[n-1]][0]);
                }
                return;
            }
    for(int i=1;i<n;++i){
        if(!viz[i]){
            viz[i]=1;
            perm[k]=i;
            if(k==1){
                if(adi[0][perm[k]])
                    bkt(k+1,adi[0][perm[k]]);
                viz[i]=0;
            }
            else{
                if(adi[perm[k-1]][perm[k]])
                    bkt(k+1,pret+adi[perm[k-1]][perm[k]]);
                viz[i]=0;
            }
        }

    }
}
int main()
{
    ios::sync_with_stdio(false);
    fin.tie(0);
    fin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        fin>>x>>y>>z;
        adi[x][y]=z;
    }
    bkt(1,0);
    if(ok)
        fout<<cost;
    else fout<<"Nu exista solutie";
    return 0;
}