#include <fstream>
#define inf 1000000000
using namespace std;

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

int n,m;
unsigned long long a[20][20];
unsigned long long cost_c,cost_m=inf;
int v[20];
bool ok;
void Read()
{
    f>>n>>m;
    int c,x,y;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        a[x][y]=c;
    }
}
bool car[20];
void solve(int i)
{
    if(i<=n)
    {
        for(int j=1;j<n;j++)
            if(!car[j] and a[v[i-1]][j])
        {
            cost_c+=a[v[i-1]][j];
            car[j]=true;
            v[i]=j;
            solve(i+1);
            car[j]=false;
            cost_c-=a[v[i-1]][j];

        }
    }
    else
    {
        if(a[v[n]][0])
        {

            if(cost_m>cost_c+a[v[n]][0])
                ok=true,cost_m=cost_c+a[v[n]][0];

        }
    }

}
int main()
{
    v[0]=0;
    car[0]=true;
    Read();
    solve(1);
    if(ok)
        g<<cost_m;
    else
        g<<"Nu exista solutie";

    return 0;
}