#include <bits/stdc++.h>
#define newline '\n'
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
///***********************
const int NMAX = 19, OO = 1e8, MAXSTATE = (1 << NMAX);
int dp[MAXSTATE][NMAX], cost[NMAX][NMAX];
int n, m, hamiltonState;
vector<int> graph[NMAX];

int main()
{
    fin >> n >> m;
    hamiltonState = (1 << n) - 1;
    for (int i = 0; i < NMAX; i++)
        for (int j = 0; j < NMAX; j++)
            cost[i][j] = OO;
    for (int i = 0; i <= hamiltonState; i++)
        for (int j = 0; j < n; j++)
            dp[i][j] = OO;
    for (int i = 1; i <= m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        graph[y].push_back(x);
        cost[x][y] = c;
    }
    dp[1][0] = 0;
    for (int st = 1; st <= hamiltonState; st++)
        for (int j = 0; j < n; j++)
            if (st & (1 << j))
                for (auto it : graph[j])
                    if (st & (1 << it))
                    {
                        int newState = st ^ (1 << j);
                        dp[st][j] = min(dp[st][j], dp[newState][it] + cost[it][j]);
                    }
    int ans = OO;
    for (auto it : graph[0])
        ans = min(ans, dp[hamiltonState][it] + cost[it][0]);
    if (ans == OO)
        fout << "Nu exista solutie";
    else
        fout << ans;
    fout << newline;
    fout.close();
    return 0;
}