#include <bits/stdc++.h>

using namespace std;

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

const int INF = 1e9;

int n, m, x, y, c, dp[(1<<18) + 2][18];
vector < pair <int, int> > a[18];

int main()
{
    in >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        in >> x >> y >> c;
        a[x].push_back(make_pair(y, c));
    }
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < (1 << n); j++)
        {
            dp[j][i] = INF;
        }
    }
    dp[1][0] = 0;
    for(int i = 1; i < (1 << n); i += 2)
    {
        for(int j = 0; j < n; j++)
        {
            for(auto it : a[j])
            {
                int v = it.first;
                int cost = it.second;
                if((1 << v))
                {
                    dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][v] + cost);
                }
            }
        }
    }
    int rezultat = INF;
    for(auto it : a[0])
    {
        int v = it.first;
        int cost = it.second;
        rezultat = min(rezultat, dp[(i << n) - 1][v] + cost);
    }
    if(rezultat == INF)
    {
        out << "Nu exista solutie";
    }
    else
        out << rezultat;
    return 0;
}