#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

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

int n, m, smin, k;

int sol[25];

bool used[25];

int cost[25][25];

vector < int > v[25];

void Generare (int nod, int sum)
{
    if (k == n && cost[sol[k]][sol[1]])
    {
        smin = min(smin, sum + cost[sol[k]][sol[1]]);
        return;
    }

    for (int i=0; i<v[nod].size(); i++)
    {
        int vecin = v[nod][i];
        int c = cost[nod][vecin];

        if (!used[vecin])
        {
            used[vecin] = 1;
            k ++; sol[k] = vecin;
            Generare(vecin, sum + c);
            k --; used[vecin] = 0;
        }
    }
}

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

    for (int i=1; i<=m; i++)
    {
        int x, y, c;
        f >> x >> y >> c;
        v[x].push_back(y);
        cost[x][y] = c;
        smin += c;
    }

    k = 1; sol[k] = 1; used[1] = 1;
    Generare(1, 0);

    g << smin;

    return 0;
}