#include <bits/stdc++.h>
#define MAX 400
#define MAX2 270000
#define INF 999999999
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
struct nod
{
    int x,cost;
};
int dp[25][MAX2];
vector<nod>c[MAX];
int n,m,mini;
int main()
{
    int i,j,mask,node,x,y,z,v;
    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>x>>y>>z;
        c[y].push_back({x,z});
    }
  for(node=0;node<n;node++)
    for(j=0;j<(1<<n);j++)
    dp[node][j]=INF;
  dp[0][1]=0;

  for(j=0; j<(1<<n); j++)
    for(node=0; node<n; node++)
       if(j&(1<<node))
        {
            for(v=0; v<c[node].size(); v++)
                if(j & (1<<(c[node][v].x)))
                    dp[node][j]=min(dp[node][j],dp[c[node][v].x][j^(1<<node)]+c[node][v].cost);
        }
    mini=INF;
    mask=(1<<n)-1;
    for(auto& it:c[0])
        mini=min(mini,dp[it.x][mask]+it.cost);
    fout<<mini;
    return 0;
}