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

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

int n,m;
unsigned long long  a[20][20],cost_c,cost_m=inf;
int v[20];
void Read()
{
    f>>n>>m;
    int c,x,y;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        x++;
        y++;
        a[x][y]=c;
    }
}
bool car[20];
void solve(int i)
{
    if(i<=n)
    {
        for(int j=2;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]][1])
        {
            if(cost_m>cost_c+a[v[n]][1])
                cost_m=cost_c+a[v[n]][1];

        }
    }

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

    return 0;
}