#include <bits/stdc++.h>
#define INF 2000000000

using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");

int n,m,dp[262200][20],p[262200];

struct elem
{
    int x,c;
};

vector<elem>a[20];

int main()
{
    int i,x,y,z,p=1,nod,stare,sol=INF;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        a[x].push_back({y,z});
    }
    for(i=1;i<=n;i++)p*=2;
    p--;
    for(stare=0;stare<=p;stare++)
        for(nod=0;nod<n;nod++)dp[stare][nod]=INF;
    dp[1][0]=0;
    for(stare=0;stare<p;stare++)
        for(nod=0;nod<n;nod++)
        if(dp[stare][nod]!=INF)
    {
        for(auto u:a[nod])
            if((stare&(1<<u.x))==0)
            dp[stare|(1<<u.x)][u.x]=min(dp[stare|(1<<u.x)][u.x],dp[stare][nod]+u.c);

    }

    for(nod=0;nod<n;nod++)
        if(dp[p][nod]!=INF)
    {
        for(auto u:a[nod])
            if(u.x==0)sol=min(sol,dp[p][nod]+u.c);
    }
    if(sol==INF)g<<"Nu exista solutie";
    else g<<sol;
    return 0;
}