#include <bits/stdc++.h>

using namespace std;

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

int a[21][21], rasp[1<<21][21];

const int INF = 1<<30;

int n, m;

signed main()
{
    in >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y, cost;
        in >> x >> y >> cost;
        a[x][y] = cost;
    }
    for(int i = 1; i < (1<<n); i++)
    {
        for(int j = 0; j < n; j++)
        {
            rasp[i][j] = INF;
        }
    }
    rasp[1][0] = 0;
    for(int mask = 1; mask < (1 << n); mask++)
    {
        for(int last = 0; last < n; last++)
        {
             if((mask & (1<<last)) != 0)
             {
                 for(int x = 0; x < n; x++)
                 {
                     if(a[last][x] && (mask&(1<<x)) == 0)
                     {
                         int nr = mask|(1<<x);
                         rasp[nr][x] = min(rasp[nr][x], rasp[mask][last] + a[last][x]);
                     }
                 }
             }
        }
    }
    int mi = INF;
    for(int i = 1; i < n; i++)
    {
        if(a[i][0])
            mi = min(mi, rasp[(1<<n) - 1][i] + a[i][0]);

    }
    if(mi == INF)
        out << "Nu exista solutie";
    else
        out << mi;
    return 0;
}