#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

const int INF = 100000000;

vector<int> v[20];
int cost[20][20];
int d[262150][20];

int main()
{
    FILE *fin, *fout;


    fin = fopen("hamilton.in", "r");
    fout = fopen("hamilton.out", "w");

    int n, m;

    fscanf(fin, "%d%d", &n, &m);

    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            cost[i][j] = INF;

    for(int i = 1; i <= m; i++)
    {
        int x, y, c;
        fscanf(fin, "%d%d%d", &x, &y, &c);
        v[y].push_back(x);
        cost[x][y] = c;
    }

    for(int i = 0; i < 1 << n; i++)
        for(int j = 0; j < n; j++)
            d[i][j] = INF;

    d[1][0] = 0;

    for(int i = 0; i < 1 << n; i++)
        for(int j = 0; j < n; j++)
        {
            if(i & (1 << j))///bitul j al lui i
                for(int k = 0; k < v[j].size(); k++)
                    if(i & (1 << v[j][k]))
                        d[i][j] = min(d[i][j], d[i ^ (1 << j)][v[j][k]] + cost[v[j][k]][j]);
        }

    int sol = INF;

    for(int i = 0; i < v[0].size(); i++)
        sol = min(sol, d[(1 << n) - 1][v[0][i]] + cost[v[0][i]][i]);

    fprintf(fout, "%d", sol);

    return 0;
}