#include <bits/stdc++.h>

using namespace std;

void initializare();

int costuri[19][19];
int dp[19][500000];
const int hi = 1<<19;
int minimul = (1 << 29);



int main() {
    ifstream f("hamilton.in");
    ofstream g("hamilton.out");
    int n, m;
    f >> n >>m;
    initializare();
    for (int i = 1; i <= m; i++){
        int x, y, cost;
        f >> x >> y >> cost;
        costuri[x][y] = cost;
    }
    for (int j = 0; j < (1 << n); j++){
        for (int i = 0; i < n; i++){
            if((1 << i) & j){
                for (int x = 0; x < n; x ++){
                    if (!((1 << x) & j)){
                        dp[x][j^(1 << x)] = min(dp[x][j^(1 << x)],dp[i][j] + costuri[i][x]);
                    }
                }
            }
        }
    }
    for (int  j = 0; j < n; j++){
        minimul = min(minimul,dp[j][(1 << n) - 1] + costuri[j][0]);
    }
    g << minimul;
    return 0;
}
void initializare(){
    for (int i = 0; i < hi; i++){
        for (int j = 0; j < 19; j ++){
            dp[j][i] = ( 1 << 29);
        }
    }
    dp[0][1] = 0;

    for (int i = 0; i < 19; i++){
        for(int j = 0; j<19; j++){
            costuri[i][j] = hi;
        }
    }
}