#include <bits/stdc++.h>

using namespace std;

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

const int INF = 100000000;
int n,m,ans=INF;
vector<int> g[22];
int dp[262150][21],cost[21][21];
int main()
{
    fin >> n >> m;
    for(int i=1; i <= m; i++)
    {
        int x,y;
        fin >> x >> y >> cost[x][y];
        g[y].push_back(x);
    }
    /// dp[masca][i] - costul minim al unui lant ce incepe in i si contine toate nodurile setate cu 1 in masca
    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(size_t k=0; k < g[j].size(); k++)
                {
                    if(i & (1<<g[j][k]))
                        dp[i][j] = min(dp[i][j],dp[i ^ (1<<j)][g[j][k]]+cost[g[j][k]][j]);
                }
            }
        }
    }
    ans = INF;
    for(size_t i = 0; i < g[0].size(); ++i)
        ans = min(ans, dp[(1<<n) - 1][g[0][i]] + cost[g[0][i]][0]);
    if (ans == INF)
        fout << "Nu exista solutie" << endl;
    else
        fout << ans << endl;
    return 0;
}