#include <bits/stdc++.h>

using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int nmax = 275000;
const int inf = 1e9+7;

int dp[nmax][19], adj[19][19], n, m, tot;

int main()
{
    fin>>n>>m;

    tot = (1<<n) - 1;
    for(int mask = 0; mask <= tot; ++mask)
    {
        for(int i = 0; i <= 18; ++i)
            dp[mask][i] = inf;
    }
    for(int i = 1; i <= n; ++i)
    {
        dp[1<<(i-1)][i] = 0;
    }

    for(int i = 1; i <= m; ++i)
    {
        int x, y, c;
        fin>>x>>y>>c;
        adj[x+1][y+1] = c;
    }

    for(int mask = 1; mask <= tot; ++mask)
    {
        for(int i = 0; (1<<i) <= mask; ++i)
        {
            if(((1<<i) & mask) == 0 || dp[mask][i+1] == inf)
                continue;
            for(int j = 0; j <= 17; ++j)
            {
                if(((1<<j) & mask) != 0 || !adj[i+1][j+1])
                    continue;

                dp[(1<<j) | mask][j+1] = min(dp[(1<<j) | mask][j+1], dp[mask][i+1] + adj[i+1][j+1]);
            }
        }
    }

    int mini = inf;
    for(int i = 1; i <= n; ++i)
    {
        if(!adj[i][1])
            continue;
        mini = min({mini, dp[tot][i] + adj[i][1]});
    }
    fout<<mini;

    return 0;
}