#include <bits/stdc++.h>
#define bigg 100000007
using namespace std;
int cost[20][20];
int dp[20][300005];
int n,m;
void lewis()
{
    for(int mask=1;mask<(1<<(n-1));mask++)
    {
        for(int i=1;i<n;i++)
        {
            dp[i][mask]=bigg;
        }
    }
    for(int i=1;i<n;i++)
    {
        if(cost[0][i]!=bigg)
            dp[i][(1<<(i-1))]=cost[0][i];
    }
    for(int mask=1;mask<(1<<(n-1));mask++)
    {
        for(int i=1;i<n;i++)
        {
            if((mask&(1<<(i-1)))!=0)
            {
                //cout<<mask<<" "<<i<<endl;
                for(int next=1;next<n;next++)
                {
                    if(cost[i][next]!=bigg&&(mask&(1<<(next-1)))==0)
                    {
                        dp[next][mask+(1<<(next-1))]=min(dp[next][mask+(1<<(next-1))],dp[i][mask]+cost[i][next]);
                       //cout<<i<<" "<<next<<" "<<dp[i][mask]<<" "<<dp[next][mask+(1<<(next-1))]<<" "<<mask<<endl;
                    }
                }
            }
           // cout<<"i: "<<i<<" "<<"mask: "<<mask<<"  dp: "<<dp[i][mask]<<'\n';
        }
    }
}
int main()
{
    ifstream cin("hamilton.in");
    ofstream cout("hamilton.out");
int x,y,c;
   cin>>n>>m;
   for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    cost[i][j]=bigg;
   for(int i=0;i<m;i++)
   {
       cin>>x>>y>>c;
       cost[x][y]=c;
   }
   lewis();
   int ans=bigg;
   for(int i=1;i<n;i++)
   {
       if(ans>dp[i][((1<<(n-1))-1)]+cost[i][0])
          ans=dp[i][((1<<(n-1))-1)]+cost[i][0];
   }
   cout<<ans;
    return 0;
}