#include <fstream>
#include <cstring>
#define inf 0x7F7F7F7F

using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int n,m,i,j,k,c[18][18],d[18][1<<18],sol;

int main(){
    memset(d,127,sizeof(d));

    fin>>n>>m;
    for(;m;m--){
        fin>>i>>j;
        fin>>c[i][j];
    }

    d[0][1]=1;
    for(j=1;j<(1<<n);j+=2)
        for(i=0;i<n;i++)
            if(d[i][j]!=inf)
                for(k=1;k<n;k++)
                    if(c[i][k]!=0 && (j&(1<<k))==0)
                        d[k][j+(1<<k)]=min(d[k][j+(1<<k)],d[i][j]+c[i][k]);

    sol=inf;
    for(i=1;i<n;i++)
        if(c[i][0]!=0)
            sol=min(sol,d[i][(1<<n)-1]+c[i][0]);

    fout<<sol;

    return 0;
}