#include    <iostream>
#include    <stdio.h>
#include    <cmath>
#include    <fstream>
#include    <vector>

using namespace std;

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

const int nMax = 20;

int n,m;

int main()
{
    fin >> n >> m;

    vector <vector<int>>G(n);
    vector <vector<int>> adj(n, vector<int>(n, 1e9));

    for(int i=0; i<m; ++i)
    {
        int x,y,z;
        fin >> x >> y >> z;
        G[y].push_back(x);
        adj[x][y] = z;
    }

    vector <vector<int>> dp(1 << n, vector<int>(n, 1e9));
    dp[1][0] = 0;

    for(int mask = 3; mask < (1 << n); mask += 2)
        for(int i=1; i<n; ++i)
            if(mask & (1 << i))
                for(auto j:G[i])
                    dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][j] + adj[j][i]);

    int sol = 1e9;

    for(int i=1; i<n; ++i)
        sol = min(sol, dp[(1 << n) - 1][i] + adj[i][0]);

    if(sol == 1e9)
        fout <<"Nu exista solutie";
    else fout << sol;

    return 0;
}