#include <bits/stdc++.h>
using namespace std;

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

int g[20][20];
int c[1 << 20][20];

int main()
{
    int x, y, cost;
    int n, m;
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y >> cost;
        g[x][y] = cost;
    }
    int nr = (1 << n) - 1;
    for(int i = 1; i <= nr; i++)
        for(int j = 0; j < n; j++)
            c[i][j] = 1e9;
    c[1][0] = 0;
    for(int st = 1; st <= nr; st++)
        for(int i = 0; i < n; i++)
            if(st & (1 << i))
                for(int j = 0; j < n; j++)
                    if(g[i][j] != 0 && !(st & (1 << j)))
                    {
                        int next = st + (1 << j);
                        c[next][j] = min(c[next][j], c[st][i] + g[i][j]);
                    }
    int minim = 1e9;
    for(int i = 1; i < n; i++)
        if(g[i][0] != 0)
            minim = min(minim, c[nr][i] + g[i][0]);
    if(minim == 1e9)
        fout << "Nu exista solutie";
    else
        fout << minim;
    return 0;
}