#include <bits/stdc++.h>

using namespace std;
vector<vector<int>> adj;
int cost[20][20];
int dp[(1<<18) + 1][19], n;
void rec(int conf, int nod){
    if(conf == (1<<n)){
        return;
    }
    int vec;
    for(int i = 0; i < adj[nod].size(); i++){
        vec = adj[nod][i];
        if(((conf>>vec)&1) == 0){
            dp[(conf | (1<<vec))][vec] = dp[conf][nod] + cost[nod][vec];
            rec((conf | (1<<vec)), vec);
        }
    }
}
int main()
{
    ifstream cin("hamilton.in");
    ofstream cout("hamilton.out");
    int m, a, b, c;
    cin >> n >> m;
    adj.resize(n + 1);
    for(int i = 0; i < m; i++){
        cin >> a >> b >> c;
        adj[a].push_back(b);
        cost[a][b] = c;
    }
    rec(1, 0);
    int ans = 2100000000;
    for(int i = 1; i < n; i++){
        if(cost[i][0] != 0)
            ans = min(ans, dp[(1<<n) - 1][i] + cost[i][0]);
    }
    cout << ans;
    return 0;
}