#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;
int n;


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


bool 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 0;
        }
    }

    if (v.size() == (size_t)n)
    {
        if (exists_edge(v[v.size() - 1], v[0]))
        {
            cost += G[v[v.size() - 1]][v[0]];
            if (cost < costmin)
            {
                costmin = cost;
            }
            return 1;
        }
        return 0;
    }

    return 1;
}

bool check(int x)
{
    for (int i = 0; i < v.size(); ++i)
    {
        if (v[i] == x)
        {
            return 0;
        }
    }
    return 1;
}

void backtrack()
{
    if (v.size() >= (size_t)n)
    {
        return;
    }

    for (int i = 0; i < n; ++i)
    {
        if (check(i))
        {
            v.push_back(i);
            if (check_path())
                backtrack();
            v.pop_back();
        }
    }
}

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 m;
    f >> n >> m;
    for (int i = 0; i < m; ++i)
    {
        int x, y, c;
        f >> x >> y >> c;
        G[x][y] = c;
    }

    backtrack();

    #define g cout
    if (costmin != 0x3f3f3f3f)
    {
        g << costmin << endl;
    }
    else
    {
        g << "Nu exista solutie" << endl;
    }

    return 0;
}