#include <bits/stdc++.h>

using namespace std;

ifstream f ("hamilton.in");
ofstream g ("hamilton.out");

int n;
int m;

struct el
{
    int nod;
    int cost;
};
vector <el> v[10005];
int dp[19][300005];
int mt[20][20];

int main()
{
    f>>n>>m;
    for(int i=1; i<=m; ++i)
    {
        int x, y, cost;
        f>>x>>y>>cost;
        v[y+1].push_back({x+1,cost});

        mt[x+1][y+1]=cost;

    }
    for(int i=0; i<(1<<(n)); ++i)
        for(int j=0; j<19; ++j)
            dp[j][i]=999999999;
    dp[1][1]=0;
  ///  for(int i=1;i<=n;++i)
  ///      dp[i][1<<(i-1)]=0;
    for(int stare=1; stare<(1<<(n)); ++stare)
    {
        for(int i=1; i<=n; ++i)
        {
            if(stare&(1<<(i-1)))
                for(int j=0; j<v[i].size(); ++j)
                    if(stare&(1<<(v[i][j].nod-1))){
                        dp[i][stare]=min(dp[i][stare],
                                         dp[v[i][j].nod][stare^(1<<(i-1))]+v[i][j].cost);
                    }

        }

    }

    int minim=9999999;
    for(int i=1;i<=n;++i)
        if(mt[i][1]!=0)
        minim=min(minim,dp[i][(1<<(n))-1]+mt[i][1]);
    g<<minim;

    return 0;
}