#include <bits/stdc++.h>
#define ll long long
#define INF 1000001
using namespace std;

ifstream fin ("hamilton.in");
ofstream fout ("hamilton.out");

int dp[272144][20];
int mat[20][20];
vector <int> gt[20];

int main()
{
    int n, m, a, b, c;
    fin>>n>>m;
    for (int i=1; i<=m; i++) {
        fin>>a>>b>>c;
        //g[a].push_back(b);
        gt[b].push_back(a);
        mat[a][b]=c;
    }
    for (int i=0; i<(1<<n); i++) {
        for (int j=0; j<n; j++) {
            dp[i][j]=INF;
        }
    }
    dp[1][0]=0;
    for (int i=1; i<(1<<n); i++) {
        for (int j=0; j<n; j++) {
            if (i&(1<<j)) {
                int iold=i-(1<<j);
                for (int vecin: gt[j]) {
                    if (iold&(1<<vecin)) {
                        dp[i][j]=min(dp[i][j], dp[iold][vecin]+mat[vecin][j]);
                    }
                }
            }
            //cout<<dp[i][j]<<' ';
        }
        //cout<<endl;
    }
    int mini=INF;
    for (int vecin : gt[0]) {
        if (dp[(1<<n)-1][vecin]+mat[vecin][0]<mini) {
            mini=dp[(1<<n)-1][vecin]+mat[vecin][0];
        }
    }
    fout<<mini;
    return 0;
}