#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define int long long
ifstream f("hamilton.in");
ofstream g("hamilton.out");
#define cin f 
#define cout g
int dp[1<<20][25],i,j,n,m,a[25][25],x,y,z; //de submultime si nodul final
vector<int> vecini[30];
signed main()
{
    cin>>n>>m;
    for(i=0;i<=24;i++){
        for(j=0;j<=24;j++){
            a[i][j]=1e15;
        }
    }
    for(i=1;i<=m;i++){ //nu am facut graf in viata mea dar nu pare atat de rau
        cin>>x>>y>>z;
        a[x][y]=z;
        vecini[x].push_back(y);
    }
    for(i=0;i<(1<<n);i++){
        for(j=0;j<=20;j++){
            dp[i][j]=1e15;
        }
    }
    int mask;
    dp[1<<0][0]=0;
    for(mask=0;mask<(1<<n);mask++){ //2 la 18 -1
        for(j=0;j<n;j++){
            if((mask&(1<<j))>0){ //ver daca este in masca
                for(auto vecin:vecini[j]){
                    if((mask&(1<<vecin))==0){ //daca nu este deja in masca                        
                    int mask2=mask+(1<<vecin);
                    dp[mask2][vecin]=min(dp[mask2][vecin],(dp[mask][j]+a[j][vecin]));
                    }
                }
            }
        }
    }
    int rez=1e15;
    for(i=0;i<n;i++){
        rez=min(rez,dp[(1<<n)-1][i]+a[i][0]);
        //cout<<dp[(1<<n)-1][i]<<"\n";
    }
    cout<<rez;
    return 0;
}