#include <fstream>
#include <math.h>
#include <string.h>
using namespace std;

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

const int INF = 2139062143;
int dp[20][262200];
int cost[20][20];
int n, m;

void init()
{
    memset(dp, 127, sizeof(dp));
    memset(cost, 127, sizeof(cost));
    dp[0][1] = 0;
}

void citire()
{
    f>>n>>m;
    int x, y, c;
    for(int i = 0; i<m; ++i)
    {
        f>>x>>y>>c;
        cost[x][y] = c;
    }
}

int calcCostMin(int i, int j)
{
    if (j & (1<<i) == 0)
        return INF;
    if(dp[i][j] == INF)
        for(int x = 0; x<n; ++x)
        {
            if(((1<<x) & j) != 0 && cost[x][i] != INF)
                dp[i][j] = min(dp[i][j], calcCostMin(x, (j^(1<<i))) + cost[x][i]);
        }
    return dp[i][j];
}

void solve()
{
    int minim = INF;
    for(int i = 1; i<n; ++i)
    {
        if(cost[i][0] != INF)
        minim = min(minim, calcCostMin(i, (1<<n)-1) + cost[i][0]);
    }
    g<<minim;
}

int main()
{
    init();
    citire();
    solve();
    return 0;
}