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

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

const int maxn = 18;
int G[maxn][maxn];
int N, M;
int a,b,c;
int dp[maxn - 1][(1 << (maxn - 1))];

int main()
{
    fin >> N >> M;
    while(M--) {
        fin >> a >> b >> c;
        G[a][b] = c;
    }
    for (int stare = 0; stare < (1 << (N - 1)); ++stare)
        for (int i = 1; i < N; ++i)
        {
            dp[i - 1][stare] = 1e9;
            if (!(stare ^ (1 << (i - 1)))) // singurul nod in stare este i
                dp[i - 1][stare] = G[0][i] == 0 ? 1e9 : G[0][i]; // costul 0 -> i daca exista
        }
    for (int stare = 0; stare < (1 << (N - 1)); ++stare)
        for (int i = 1; i < N; ++i)
        {
            if(!(stare & (1 << (i - 1)))) continue; // i nu este in stare
            for (int j = 1; j < N; ++j)
            {
                if (stare & (1 << (j - 1)))
                    continue; // j este deja in stare
                if(!G[i][j]) continue; // nu este conexiune i -> j
                dp[j - 1][stare | (1 << (j - 1))] = min(
                    dp[j - 1][stare | (1 << (j - 1))],
                    dp[i - 1][stare] + G[i][j]);
            }
        }
    int costMin = 1e9;
    for(int i = 1; i < N; ++i)
    {
        if (!G[i][0]) continue;
        costMin = min(costMin, dp[i - 1][(1 << (N - 1)) - 1] + G[i][0]);
    }
    fout << costMin;
}