#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int cost[20][20], din[(1<<17)+5][19];
int n, m, i, x, y, c, mn, node, node2, mni;
long long stare;

int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        cost[x][y]=c;
    }
    for(stare=1;stare<=(1<<n)-1;stare++)
    {
        for(x=0;(1<<x)<=stare;x++)
        {
            if((1<<x)&stare)
            {
                mn=999999;
                node=x+1;
                if((1<<x)==stare&&cost[0][node])
                {
                    mn=cost[0][node];
                }
                for(node2=1;node2<n;node2++)
                {
                    if(din[stare-(1<<x)][node2]&&cost[node2][node])
                    {
                        if(din[stare-(1<<x)][node2]+cost[node2][node]<mn)
                            mn=din[stare-(1<<x)][node2]+cost[node2][node];
                    }
                }
                if(mn!=999999)
                    din[stare][node]=mn;
            }
        }
    }
    mn=999999;
    for(i=1;i<n;i++)
    {
        if(din[(1<<(n-1))-1][i]&&din[(1<<(n-1))-1][i]<mn&&cost[i][0])
        {
            mn=din[(1<<(n-1))-1][i];
            mni=i;
        }
    }
    if(mn!=999999)
        fout<<mn+cost[mni][0];
    else
        fout<<"Nu exista solutie";
    return 0;
}