#include <cstdio>
#include <vector>
using namespace std;
const int N = 19;
long long d[1 << N][N], cost[N][N];
vector<int> a[N];
int n, m;
const long long INF = 0x3f3f3f3f;
inline long long min (long long  a, long long b) {
    return a < b ? a : b;
}

int main() {
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);
    int i, j, x, y, ct, k;
    scanf("%d %d", &n, &m);
    for(i = 1; i <= m; ++i){
        scanf("%d %d %d", &x, &y, &ct);
        a[y].push_back(x);
        cost[x][y] = ct;
    }

    for(i = 0; i < (1 << n); ++i)
        for(j = 0; j <= n; ++j)
            d[i][j] = INF;
    d[1][0] = 0;

    for(i = 1; i < (1 << n); ++i)
        for(j = 0; j <= n; ++j)
            if((1 << j) & i){
                for(k = 0; k < a[j].size(); ++k)
                    if(i & (1 << a[j][k]))
                        d[i][j] = min(d[i][j], d[i ^ (1 << j)][ a[j][k] ] + cost[ a[j][k] ][j]);
            }
   // return 0;
    long long sol = INF;
    for(i = 0; i < a[0].size(); ++i)
        sol = min(sol, d[(1 << n) - 1][a[0][i]] + cost[a[0][i]][0]);

    printf("%lld\n", sol);

    return 0;
}