#include <bits/stdc++.h>

using namespace std;

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

struct muchii{
    int node, cost;
};

int n,m,x,y,z,minim,dp[300000][20];
vector <muchii> edges[20];

int32_t main()
{
    f>>n>>m;
    for(int i=1; i<=m; i++)
        f>>x>>y>>z, edges[x].push_back({y,z});
    for(int masca=1; masca<=(1<<n)-1; masca++)
        for(int i=0; i<n; i++)
            dp[masca][i]=INT_MAX;
    dp[1][0]=0, minim=INT_MAX;
    for(int masca=1; masca<(1<<n)-1; masca++)
    {
        for(int i=0; i<n; i++)
            if(masca&(1<<i) and dp[masca][i]!=INT_MAX)
                for(auto j:edges[i])
                {
                    int fakemasca=masca|(1<<j.node);
                    dp[fakemasca][j.node]=min(dp[fakemasca][j.node],dp[masca][i]+j.cost);
                }
    }
    for(int i=1; i<n; i++)
        for(auto j:edges[i])
            if(j.node==0 and dp[(1<<n)-1][i]!=INT_MAX)
                minim=min(minim,dp[(1<<n)-1][i]+j.cost);
    g<<minim;
    return 0;
}