#include <bits/stdc++.h>
//#define dim 2002
using namespace std;
ifstream fin ("hamilton.in");
ofstream fout("hamilton.out");
int n,put[22],dp[19][262145];
const int inf=2000000000;

struct el
{
    int nod,cost;
};
vector<el> a[19];


void rezolva ()
{
    int i,st,sol=inf;
    for (i=1; i<=n; i++)
        for (st=1; st<=put[n]-1; ++st)
            dp[i][st]=inf;
    dp[1][1]=0;
    for (st=1; st<put[n]-1; st++)
        for (i=1; i<=n; i++)
            if (dp[i][st]!=inf)
                for (auto y:a[i])
                    if ((st&put[y.nod-1])==0)
                    dp[y.nod][st|put[y.nod-1]]=min(dp[y.nod][st|put[y.nod-1]],dp[i][st]+y.cost);
    for (i=1; i<=n; i++)
        if (dp[i][st]!=inf)
            for (auto y:a[i])
                if (y.nod==1)
                    sol=min(sol,dp[i][st]+y.cost);
    if (sol==inf)
        fout<<"Nu exista solutie";
    else    fout<<sol;
}

int32_t main()
{
    int i,m,x,y,z;
    fin>>n>>m;
    put[0]=1;
    for (i=1; i<=20; i++)
        put[i]=put[i-1]*2;
    for (i=1; i<=m; i++)
    {
        fin>>x>>y>>z;
        x++,y++;
        a[x].push_back({y,z});
    }
    rezolva();
    return 0;
}