#include <iostream>
#include <cstdio>
#include <vector>

#define INF 0x3f3f3f3f

using namespace std;

int c[20][20];
int dp[20][1<<18];
vector <int> g[20];
int n,m,x,y,lc;

int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);

    scanf("%d%d", &n,&m);
    for(int i = 0; i < m; ++i){
        scanf("%d%d%d", &x,&y,&lc);
        c[x][y] = lc;
        g[y].push_back(x);
    }

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

    for(int i = 0; i < (1<<n); ++i)
        for(int j = 0; j < n; ++j)
            if(i&(1<<j))
                for(int k : g[j])
                    if(i&(1<<k))
                        dp[j][i] = min(dp[j][i],
                        dp[k][i^(1<<j)]+c[k][j]);

    int rez = INF;
    for(int i = 0; i < n; ++i)
        if(c[i][0])
            rez = min(rez, dp[i][(1<<n)-1]+c[i][0]);

    cout<<rez;

    return 0;
}