#include <bits/stdc++.h>
using namespace std;
#ifdef INFOARENA
#define cout fout
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
#else
ifstream fin("date.in");
#endif // INFOARENA

/// ///////////////////////////////////////////

void read();

#define nmax 18
#define inf 0x3f3f3f3f

int n,dist[1<<nmax][nmax];
struct eee{int nod,dist;};
vector<eee> G[nmax];

int get_dist(int nod,int conf)
{
    if(dist[conf][nod]!=-1) return dist[conf][nod];

    dist[conf][nod]=inf;
    for(auto ant:G[nod])
    {
        if(ant.nod==0 && conf!=(1<<nod)+1) continue;
        if(conf&(1<<ant.nod))
            dist[conf][nod]=min(dist[conf][nod],get_dist(ant.nod,conf^(1<<nod)) + ant.dist);
    }
    return dist[conf][nod];
}

int main()
{
    read();

    int conf=(1<<n)-1;

    memset(dist,-1,sizeof dist);
    dist[1][0]=0;

    int res=inf;
    for(auto ant:G[0])
        res=min(res,get_dist(ant.nod,conf)+ant.dist);

    if(res==inf) cout<<"Nu exista solutie";
    else cout<<res;
}
void read()
{
    int x,y,c,m;
    fin>>n>>m;
    for(;m;--m)
    {
        fin>>x>>y>>c;
        G[y].push_back({x,c});
    }
}