#include <bits/stdc++.h>
#define INF 1000000000

using namespace std;

int n,Cost[20][20],dp[(1<<18)][20];

int main()
{
    int m,x,y,c,sol=INF,i,j,k;
    ifstream cin("hamilton.in");
    ofstream cout("hamilton.out");
    cin>>n>>m;
    while(m--)
    {
        cin>>x>>y>>c;
        Cost[x][y]=c;
    }
    for(i=0;i<(1<<n);++i)
        for(j=0;j<n;++j) dp[i][j]=INF;
    dp[1][0]=0;
    for(i=1;i<(1<<n);++i)
        for(j=0;j<n;++j)
        {
            if(dp[i][j]==INF) continue;
            for(k=0;k<n;++k)
                if(!((1<<k)&i) && Cost[j][k]) dp[i+(1<<k)][k]=min(dp[i+(1<<k)][k],dp[i][j]+Cost[j][k]);
        }
    for(i=1;i<n;++i)
        if(Cost[i][0]) sol=min(sol,dp[(1<<n)-1][i]+Cost[i][0]);
    cout<<sol;
    return 0;
}