#include <bits/stdc++.h>
#define inf (1 << 29)

using namespace std;

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

int n, m, dist[20][20], dp[20][(1 << 18)], maxMask;

void Citire()
{
    int x, y, c;

    fin >> n >> m;
    maxMask = (1 << n) - 1;

    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            dist[i][j] = inf;

    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y >> c;
        dist[x][y] = c;
    }
}

void Rez()
{
    for(int i = 0; i < n; i++)
        for(int j = 1; j <= maxMask; j++)
            dp[i][j] = inf;

    dp[0][1] = 0;
    for(int i = 1; i <= maxMask; i++)
        for(int j = 0; j < n; j++)
            if((i & (1 << j)) > 0)
                for(int k = 0; k < n; k++)
                    if((i & (1 << k)) == 0)
                        dp[k][(i | (1 << k))] = min (dp[k][(i | (1 << k))], dp[j][i] + dist[j][k]);

    int minim = inf;
    for(int i = 0; i < n; i++)
        minim = min(minim, dp[i][maxMask] + dist[i][0]);

    if(minim == inf)
        fout << "Nu exista solutie\n";
    else fout << minim << "\n";
}

int main()
{
    Citire();
    Rez();
    return 0;
}