#include <bits/stdc++.h>

using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

const int Nmax = 19;
const int Vmax = (1e6 * 18) + 1;

int n, m;

vector<pair<int, int>> grafTrans[Nmax];

int dp[Nmax][Nmax];

int ans = Vmax;

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        int x, y, c;
        fin >> x >> y >> c;

        grafTrans[y].push_back({x, c});
    }

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

    dp[(1 << 0)][0] = 0;

    for(int i = 0; i <= (1 << n) - 1; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            for(auto v : grafTrans[j])
            {
                auto vecin = v.first;
                auto cost = v.second;

                if(i & (1 << j))
                    dp[i][j] = min(dp[i - (1 << j)][vecin] + cost, dp[i][j]);
            }
        }
    }

    for(auto v : grafTrans[0])
    {
        auto vecin = v.first;
        auto cost = v.second;

        ans = min(ans, dp[(1 << n) - 1][vecin] + cost);
    }

    fout << ans;

    return 0;
}