#include <iostream>
#include <fstream>
using namespace std;

int n, m, sol;
int cost[20][20];
int solutii[20][1<<20];

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

void citeste ()
{
    f>>n>>m;
    int a, b, c;
    for (int i=1; i<=m; i++)
    {
        f>>a>>b>>c;
        a++; b++;
        cost[a][b]=c;
    }
}


int back (int nodanterior, int x)
{
    if (solutii[nodanterior][x]!=0)
    {
        return solutii[nodanterior][x];
    }
    else
    {
        if (x==(1<<n+1)-2)
        {
            //cout<<x<<' '<<;
            if(cost[nodanterior][1] != 0)
                solutii[nodanterior][x] = cost[nodanterior][1];
            else
                solutii[nodanterior][x] = 0x3fffffff;
        }
        else
        {
            int minim, sol;
            minim=0x3fffffff;
            for (int i=2; i<=n; i++)
            {
                if (cost[nodanterior][i]!= 0 && (x & (1<<i)) == 0)
                {
                    sol=cost[nodanterior][i]+back (i, x ^ (1<<i));
                    if (minim>sol) minim=sol;
                }
            }
            solutii[nodanterior][x]=minim;
        }
        return solutii[nodanterior][x];
    }
}

int main ()
{
    citeste ();
    sol=back (1, 1 << 1);
    if (sol==0x3fffffff) g<<"Nu exista solutie";
    else g<<sol;
    return 0;
}