#include <bits/stdc++.h>

using namespace std;

ifstream in("hamilton.in");
ofstream out("hamilton.out");
int n, m, dp[18][1<<18];
vector <pair<int, int>> gft[18];

int main()
{
    in >> n >> m;
    
    for(int i, j, ct, k = 1; k <= m; k++)
    {
        in >> i >> j >> ct;
        gft[j].push_back({i, ct});
    }
    
    for(int i = 0; i < n; i++)
        for(int j = 0; j < (1<<n); j++)
            dp[i][j] = 1 << 25;
            
    dp[1][2] = 0;
    
    for(int j = 1; j < (1<<n); j++)
        for(int i = 0; (1<<i) <= j; i++)
            if(j & (1<<i))
                for(auto nod:gft[i])
                    if(j & (1<<nod.first))
                        dp[i][j] = min(dp[i][j], dp[nod.first][j-(1<<i)] + nod.second);
                   
    int minim = 1 << 25;
    
    for(auto nod:gft[1])
        minim = min(minim, dp[nod.first][(1<<n)-1] + nod.second);
        
    if(minim == (1<<25))
        out << "Nu exista solutie";
    else
        out << minim;
        
    return 0;
}