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

#define mp make_pair
#define x first
#define y second

using namespace std;


int G[20][20];
int costmin = 0x3f3f3f3f;
vector<int> v;


bool exists_edge(int x, int y)
{
    return (G[x][y] != -1);
}


void check_path()
{
    int cost = 0;
    for (size_t i = 0; i < v.size() - 1; ++i)
    {
        if (exists_edge(v[i], v[i+1]))
        {
            cost += G[v[i]][v[i+1]];
        }
        else
        {
            return;
        }
    }
    if (exists_edge(v[v.size() - 1], v[0]))
    {
        cost += G[v[v.size() - 1]][v[0]];
        if (cost < costmin)
        {
            costmin = cost;
        }
    }
}

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

    for (int i = 0; i < 20; ++i)
    {
        for (int j = 0; j < 20; ++j)
        {
            G[i][j] = -1;
        }
    }

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

    for (int i = 0; i < n; ++i)
    {
        v.push_back(i);
    }

    do
    {
        check_path();
    }
    while (next_permutation(v.begin(), v.end()));

    g << costmin << endl;

    return 0;
}