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

int c[25][25], dp[19][(1<<18) + 5], n, m, x, y, cost;
int main()
{
    ifstream f("hamilton.in");
    ofstream g("hamilton.out");

    f >> n >> m;
    for(int i = 0; i <= n + 1; i ++)
        for(int j = 0; j <= n + 1; j ++)
            c[i][j] = 1e9;
    for(int i = 0; i <= n; i ++)
        for(int j = 0; j < (1 << n); j ++)
            dp[i][j] = 1e9;

    for(int i = 0; i < m; i ++)
    {
        f >> x >> y >> cost;
        c[x][y] = cost;
    }
    dp[0][1] = 0;
    for(int mask = 1; mask < (1<<18); mask ++)
        for(int i = 0; i < n; i ++)
        {
            if(mask & (1 << i))
            {
                int prev = mask ^ (1 << i);
                for(int j = 0; j < n; j ++)
                    if(mask & (1 << j))
                        dp[i][mask] = min(dp[i][mask], dp[j][prev] + c[j][i]);
            }
        }
    int minn = 1e9, m = (1 << n) - 1;
    for(int i = 1; i < n; i ++)
        minn = min(minn, dp[i][m] + c[i][0]);
    g << minn;
    return 0;
}