#include <cstdio>
#include <vector>
using namespace std;
int n,m;
vector<int>adj[20],cost[20];
bool vis[10000];
int minim=100000000;
void dfs(int nod,int costi,int vizitate)
{
     vis[nod]=1;
     vector<int>::iterator it1,it2;
     if(vizitate==n)
     {
                    it2=cost[nod].begin();
                    for(it1=adj[nod].begin();it1!=adj[nod].end();++it1)
                    {
                           if(*it1==0)
                           {
                                      if(minim>costi+*it2) minim=costi+*it2;
                                      break;
                           }
                           ++it2;
                    }
     } 
     else
     {
     it2=cost[nod].begin();
     for(it1=adj[nod].begin();it1!=adj[nod].end();++it1)
     {
                                                              if(vis[*it1]==0) dfs(*it1,costi+*it2,vizitate+1);
                                                              ++it2;
     }
     }
     vis[nod]=0;
}
int main()
{
    freopen ("hamilton.in","r",stdin);
    freopen ("hamilton.out","w",stdout);
    scanf("%d%d",&n,&m);
    int p1,p2,c;
    for(int i=1;i<=m;i++)
    {
            scanf("%d%d%d",&p1,&p2,&c);
            adj[p1].push_back(p2);
            cost[p1].push_back(c);
    }
    dfs(0,0,1);
    printf("%d\n",minim);
}