#include <iostream>
#include <fstream>

using namespace std;

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

const int N = 19, INF = (1 << 30) - 1;
int dp[1 << N][N], c[N][N];

bool apartine(int x, int multime)
{
    return ((1 << x) & multime) == 1 << x;
}

int diferenta(int multime, int x)
{
    return (multime ^ (1 << x));
}

void scrie(int v[], int n)
{
    for (int i = 0; i < n; i++)
    {
        out << v[i] << "\t\t";
    }
    out << "\n";
}

int main()
{
    int n, m;
    in >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i != j) c[i][j] = INF;
        }
    }
    for(int i = 0; i < m; i++)
    {
        int x, y, z;
        in >> x >> y >> z;
        c[x][y] = z;
    }
    for(int i = 1; i < 1 << n; i++)
        for(int j = 0; j < n; j++)
            dp[i][j] = INF;
    dp[1][0] = 0;
    for (int i = 3; i < (1 << n); i += 2)
    {
        for(int j = 1; j < n; j++)
        {
            if (apartine(j, i))
            {
                for(int k = 0; k < n; k++)
                {
                    int ii = diferenta(i, j);
                    if (apartine(k, ii))
                    {
                        dp[i][j] = min(dp[i][j], dp[ii][k] + c[k][j]);
                    }
                }
            }
        }
        //scrie(dp[i], n);
    }

    int rez = INF;

    for(int j = 0; j < n; j++)
    {
        rez =  min(dp[(1<<n)-1][j] + c[j][0], rez);
    }
    if(rez == INF){
        fout << "Nu exista solutie";
    }
    else{
        out << rez;
    }

    return 0;
}