#include <bits/stdc++.h>

using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int dp[(1 << 18) + 5][19];
int G[20][20];
int main()
{
    int n,i,m,u,v,c,j;
    fin >> n >> m;
    for(i = 0; i < n; i++){
        for(j = 0; j < n; j++) G[i][j] = 1e8;
        for(j = 0; j < (1 << n); j++) dp[j][i] = 1e8;
    }

    for(i = 1; i <= m; i++){
        fin >> u >> v >> c;
        G[u][v] = c;
    }
    dp[1][0] = 0;
    for(int k = 1; k < (1 << n); k++){
        for(i = 0; i < n; i++){
            if((1 << i) & k){
                for(j = 0; j < n; j++){
                    if((1 << j) & k) dp[k][i] = min(dp[k][i], dp[k ^ (1 << i)][j] + G[j][i]);
                }
            }
        }
    }
    int rez = 2 * 1e9;
    for(i = 0; i < n; i++) rez = min(rez, dp[(1 << n) - 1][i] + G[i][0]);
    fout << rez;
    return 0;
}