#include <bits/stdc++.h>
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int fv[100009];;
int dp[300009][20];
int p[30];
signed main ()
{
    int n, m;
    p[0]=1;
    for (int i=1; i<=20; i++)
        p[i]=2*p[i-1];
    f >> n >> m;
    for (int i=1; i<=m; i++)
    {
        int x, y;
        f >> x >> y;
        //x++, y++;
        int z;
        f >> z;
        fv[x*30+y]=z;
        //fv[ {y,x}]=z;
    }
    for (int i=0; i<=(1<<n); i++)
        for (int j=0; j<=n; j++)
        dp[i][j]=1e9;
    //for (int i=0; i<n; i++)
        dp[1][0]=0;
    for (int stare=0; stare<p[n]; stare++)
    {
        for (int i=0; p[i]<=stare; i++)
        {
            if ((stare&p[i]))
            {
                for (int j=0; j<n; j++)
                {
                    if ((stare&p[j])==0 && fv[i*30+j])
                    {
                        int ns=(stare|p[j]);
                        dp[ns][j]=min (dp[ns][j], dp[stare][i]+fv[i*30+j]);
                    }
                }
            }
        }
    }
    int minim=1e9;
    for (int i=0; i<n; i++)
    {
        if (fv[i*30])
            minim=min (minim, dp[p[n]-1][i]+fv[i*30]);
        //cout << minim<<'\n';
    }
    if (minim!=1e9) g << minim;
    else g << "Nu exista solutie";
}