#include <bits/stdc++.h>

using namespace std;

#define N 20
#define M 4000

const int INF = INT_MAX;
int n, dp[(1 << N)][N];

int A[N][N];

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

    int m, x, y, c;
    fin >> n >> m; do {
        fin >> x >> y >> c;
        A[x][y] = c;
    } while(--m);

    dp[1][0] = 0;
    for(int i = 1; i <= n; ++i) dp[1][i] = INF;

    for(int i = 3; i <= (1<<n)-1; ++i)
        for(int j = 0; j < n; ++j) {
            if((1 << j) & i) {
                int i_prim = (i ^ (1 << j));
                dp[i][j] = INF;
                for(int k = 0; k < n; ++k) 
                    if(((1 << k) & i) && A[k][j] && dp[i_prim][k] != INF)
                        dp[i][j] = min(dp[i][j], dp[i_prim][k] + A[k][j]);
            }
        }
    
    int rez = INF;
    for(int j = 0; j < n; ++j)
		if(A[j][0] && dp[(1<<n)-1][j] != INF)
        rez = min(rez, dp[(1<<n)-1][j] + A[j][0]);
    fout << rez;
}