//#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream in("hamilton.in");
ofstream out("hamilton.out");
vector < pair < int , int > > v[20];
int viz[20],cm=INT_MAX,n,m;
void dfs(int nod,int nr,int cost)
{
   viz[nod]=1;
   for(int i=0;i<v[nod].size();i++)
   {
     int vecin=v[nod][i].first;
     if(!viz[vecin])
         dfs(vecin,nr+1,cost+v[nod][i].second);

         if(nr==n && v[nod][i].first==1)
            cm=(cm,cost+v[nod][i].second);
   }
     viz[nod]=0;

}
void citire()
{
    in>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z; in>>x>>y>>z; x++,y++;
        v[x].push_back({y,z});
    }
}

int main()
{
   citire();
   dfs(1,1,0);
   out<<cm;
    return 0;
}