#include <iostream>
#include <bits/stdc++.h>
#define NM 19
#define inf 1000000000
#define pb push_back
using namespace std;
ifstream in("hamilton.in");
ofstream out("hamilton.out");
int dp[(1<<NM)+5][NM],cst[NM][NM],a,b,c,n,m,minn=inf;
vector<int> v[NM];
int main()
{
    in>>n>>m;
    for(int i=1;i<=m;++i)
    {
        in>>a>>b>>c;
        cst[a][b]=c;
        v[a].pb(b);
    }
    for(int mask=0;mask<(1<<n);++mask)
        for(int j=0;j<n;++j)dp[mask][j]=inf;
    dp[0][0]=0;
    for(int mask=0;mask<(1<<n);++mask)
        for(int nod=0;nod<n;++nod)
            for(auto vecin:v[nod])
                if((mask&(1<<vecin)))
                    dp[mask][vecin]=min(dp[mask][vecin],dp[mask-(1<<vecin)][nod]+cst[nod][vecin]);
    for(int i=0;i<n;++i)minn=min(minn,dp[(1<<n)-1][i]);
    out<<minn;
    return 0;
}