#include <bits/stdc++.h>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int NMAX = 19, INF = 1e9, MASK = 262144; /// (1 << 18)
vector<int> in[NMAX];
int cost[NMAX][NMAX], dp[MASK][NMAX], n, m;

int hamilton()
{
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cost[i][j] = (cost[i][j] == 0 ? INF : cost[i][j]);
    for(int i = 0; i < (1 << n); i++)
        for(int j = 0; j < n; j++)
            dp[i][j] = INF;
    dp[1][0] = 0;
    for(int i = 0; i < (1 << n); i++)
        for(int j = 0; j < n; j++)
            if(i & (1 << j))
                for(int k = 0; k < in[j].size(); k++)
                    if(i & (1 << in[j][k]))
                        dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][in[j][k]] + cost[in[j][k]][j]);
    int ret = INF;
    for(int i = 0; i < in[0].size(); i++)
        ret = min(ret, dp[(1 << n) - 1][in[0][i]] + cost[in[0][i]][0]);
    return ret;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr);

    fin >> n >> m;
    while(m--)
    {
        int x, y;
        fin >> x >> y >> cost[x][y];
        in[y].push_back(x);
    }
    int ans = hamilton();
    if(ans == INF)
        fout << "Nu exista solutie";
    else
        fout << ans;

    return 0;
}