#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;
    int lim = 1 << n;
    for(int conf = 1; conf < lim; conf++)
        for(int nod = 0; nod < n; nod++)
            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);
    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;
}