#include <cstdio>
#include <vector>
#include <algorithm>
#include <climits>

FILE *f=fopen("hamilton.in","r");
FILE *g=fopen("hamilton.out","w");

#define v first
#define cost second

using namespace std;
const int inf=INT_MAX/2;

vector<pair<int,int> > lv[20];
int d[19][19],n,m,used[20];

void get_graph()
{
    int a,b,c;
    fscanf(f,"%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        fscanf(f,"%d%d%d",&a,&b,&c);
        a++,b++;
        lv[a].push_back(make_pair(b,c));
        d[a][b]=c;
    }
}
int costmin=inf;
void DFS(int k,int nrn,int c)
{
    vector<pair<int,int> > ::iterator it;
    used[k]=1;
    if(nrn==n &&d[k][1]!=0 && c <costmin+d[k][1])costmin=c+d[k][1];
    for(it=lv[k].begin(); it!=lv[k].end();++it)
    if(!used[it->v])
    {
        DFS(it->v,nrn+1,c+it->cost);
        used[it->v]=0;
    }
}
int main()
{
    get_graph();
    DFS(1,1,0);
    fprintf(g,"%d",costmin);
    return 0;
}