#include <fstream>
#include <algorithm>
#include <vector>
#include <array>
#include <cstring>
using namespace std;

ifstream cin("hamilton.in");
ofstream cout("hamilton.out");

const int NMAX=18;
const int INF=1e9;

int n, m, dp[(1<<(NMAX+1))][NMAX+1], a[NMAX+1][NMAX+1];

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x, y, c;
        cin>>x>>y>>c;
        a[x][y]=c;
    }
    for(int i=1;i<(1<<n);i++){
        for(int j=0;j<n;j++){
            dp[i][j]=INF;
        }
    }
    dp[1][0]=0;
    for(int mask=1;mask<(1<<n);mask++){
        for(int x=0;x<n;x++){
            if(mask&(1<<x)){
                for(int y=0;y<n;y++){
                    if(mask&(1<<y)&&a[y][x]!=0){
                        dp[mask][x]=min(dp[mask][x], dp[mask^(1<<x)][y]+a[y][x]);
                    }
                }
            }
        }
    }
    int Min=INF;
    for(int x=1;x<n;x++){
        if(a[x][0]!=0){
            Min=min(Min, dp[(1<<n)-1][x]+a[x][0]);
        }
    }
    cout<<Min;
}