#include <bits/stdc++.h>

using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int INF = 1e9;

int main()
{
    int n, m, x, y, d;
    fin >> n >> m;
    vector <vector <pair <int, int>>> ad(n);
    vector <pair <int, int>> in;
    for(int i = 0; i < m; i++){
        fin >> x >> y >> d;
        ad[x].push_back({y, d});
        if(y == 0)
        in.push_back({x, d});
    }
    vector <vector <int>> dp(1 << n, vector <int>(n, INF));
    dp[1][0] = 0;
    queue <pair<int, int>> q;
    q.push({1, 0});
    while(q.size() > 0){
        int conf = q.front().first, nod = q.front().second;
        q.pop();
        for(auto fiu : ad[nod])
            if((conf & (1 << fiu.first)) == 0){
                dp[conf | (1 << fiu.first)][fiu.first] = min(dp[conf | (1 << fiu.first)][fiu.first], dp[conf][nod] + fiu.second);
                q.push({conf | (1 << fiu.first), fiu.first});
            }
    }
    int conf = (1 << n) - 1, ans = INF;
    for(auto e : in)
        ans = min(ans, dp[conf][e.first] + e.second);
    fout << ans;
    fin.close();
    fout.close();
    return 0;
}