#include <bits/stdc++.h>

using namespace std;

vector <int> graff[19];
int costuri[20][20];
long long dp[1 << 20][20];
const int hi = 1<<20;
long long minimul = 1LL * hi * hi;

void initializare(){
    for (int i = 0; i < hi; i++){
        for (int j = 0; j < 20; j ++){
            dp[i][j] = ( 1 << 29);
        }
    }
    dp[1][0] = 0;

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


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;
        graff[x].push_back(y);
        costuri[x][y] = cost;
    }
    for (int j = 0; j < (1 << n); j++){
        for (int i = 0; i < n; i++){
            if((1 << i) & j){
                for (auto x : graff[i]){
                    if (!((1 << x) & j)){
                        dp[j^(1 << x)][x] = min(dp[j^(1 << x)][x],dp[j][i] + costuri[i][x]);
                    }
                }
            }
        }
    }
    for (int  j = 0; j < n; j++){
        minimul = min(minimul,dp[(1 << n) - 1][j] + costuri[j][0]);
    }
    g << minimul;
    return 0;
}