#include <bits/stdc++.h>
using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");

const int NMax = 19;
const int inf = 0x3f3f3f3f;

int dp[1 << NMax][NMax];
vector < int > graf[NMax];
int n, m, cost[NMax][NMax];

int main()
{
    int x, y, c;
    f >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        f >> x >> y >> c;
        graf[y].push_back(x);
        cost[y][x] = c;
    }

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

    dp[1][0] = 0;
    for(int i = 0; i < (1 << n); ++i)
        for(int j = 0; j < n; ++j)
        {
            if((1 << j) & i)
            {
                for(int k = 0; k < graf[j].size(); ++k)
                {
                    if((1 << graf[j][k]) & i)
                    {
                        dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][graf[j][k]] + cost[j][graf[j][k]]);
                    }
                }
            }
        }
    int sol = inf;
    for(int i = 0; i < graf[0].size(); ++i)
        sol = min(sol, dp[(1 << n) - 1][graf[0][i]] + cost[0][graf[0][i]]);
    g << sol;
}