#include <bits/stdc++.h>
#define max32 200000000

std::vector<int> cst[18][2];

int h[1<<18][18];

int mn(int a,int b)
{
    if(a<b)
        return a;
    return b;
}

int main()
{
    int n,m,i,a,b,c,j,m2,q,best;
    FILE*fi,*fo;
    fi=fopen("hamilton.in","r");
    fo=fopen("hamilton.out","w");
    fscanf(fi,"%d%d",&n,&m);
    for(i=0; i<m; i++)
    {
        fscanf(fi,"%d%d%d",&a,&b,&c);
        cst[b][0].push_back(a);
        cst[b][1].push_back(c);
    }
    for(i=0; i<1<<18; i++)
        for(j=0; j<18; j++)
            h[i][j]=max32;
    h[0][0]=0;
    for(i=1; i<1<<n; i++)
    {
        for(j=1; j<n; j++)
        {
            if(i&(1<<(j-1)))
            {
                m2=i^(1<<(j-1));
                for(q=0; q<cst[j][0].size(); q++)
                {
                    h[i][j]=mn(h[i][j],h[m2][cst[j][0][q]]+cst[j][1][q]);
                }
            }
        }
    }
    best=max32;
    for(i=0; i<cst[0][0].size(); i++)
    {
        best=mn(best,h[(1<<(n-1))-1][cst[0][0][i]]+cst[0][1][i]);
    }
    fprintf(fo,"%d",best);
    fclose(fi);
    fclose(fo);
    return 0;
}