#include <cstring>

#include <fstream>
#include <vector>
using namespace std;

const int MAX_N = 20;
const int INF = 0x3f3f3f3f;
const int MAX_C = (1 << 18) + 2;

int N, M, x, y;
int Cost[MAX_N][MAX_N], B[MAX_C][MAX_N];
vector < int > v[MAX_N];

int main()
{
    ifstream f("hamilton.in");
    ofstream g("hamilton.out");
    
    memset(Cost, INF, sizeof(Cost));
    
    f >> N >> M;
    for(int i = 1; i <= M; ++i)
        f >> x >> y, f >> Cost[x][y], v[y].push_back(x);
    
    memset(B, INF, sizeof(B));
    B[1][0] = 0;
    for(int i = 1; i < (1 << N); ++i)
        for(int j = 0; j < N; ++j)
            if(i & (1 << j))
            {
                for(int k = 0; k < v[j].size(); ++k)
                    if(i & (1 << v[j][k]))
                        B[i][j] = min(B[i][j], B[i^(1 << j)][ v[j][k] ] + Cost[ v[j][k] ][j]);
            }

    int Res = INF;
    for(int i = 0; i < v[0].size(); ++i)
        Res = min(Res, B[ (1 << N) - 1 ][ v[0][i] ]  + Cost[ v[0][i] ][0]);    
 
    if(Res == INF)
        g << "Nu exista solutie" << '\n';
    else g << Res << '\n';
        
    f.close();
    g.close();

    return 0;
}