#include <iostream>
#include <fstream>

using namespace std;

struct lst
{
    int dst,cst;
    lst *urm;
}*t;

struct nod
{
    lst *p,*u;
    int prez;
}v[20];

int n,m,i,j,k,l,sol;

fstream f,g;

void bkt(int i, int l, int s)
{
    lst *t;
    l++;
    v[i].prez=1;
    if(l==n)for(t=v[i].p;t!=NULL;t=t->urm)
    {
        if(t->dst==0)sol=min(sol,s+t->cst);
    }
    else for(t=v[i].p;t!=NULL;t=t->urm)if(v[t->dst].prez==0)bkt(t->dst,l,s+t->cst);
    v[i].prez=0;
}

int main()
{
        f.open("hamilton.in",ios_base::in);
        g.open("hamilton.out",ios_base::out);
        f>>n>>m;
        for(i=1;i<=m;i++)
        {
            f>>j>>k>>l;
            t=new lst;
            t->dst=k;
            t->cst=l;
            t->urm=NULL;
            if(v[j].p==NULL)v[j].p=t;
            else v[j].u->urm=t;
            v[j].u=t;
        }
        sol=18000001;
        bkt(0,0,0);//nod poz, noduri parcurse, cost acumulat
        g<<sol;
}