#include<fstream>
#define INF 1000000000
using namespace std;
int n, m, i, j, k, x, y, z, sol;
int a[(1 << 18)][20], c[20][20];
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int main(){
    fin>> n >> m;
    for(i = 1; i <= m; i++){
        fin>> x >> y >> z;
        c[x][y] = z;
    }
    for(i = 1; i < (1 << n); i++){
        for(j = 0; j < n; j++){
            a[i][j] = INF;
        }
    }
    for(j = 0; j < n; j++){
        a[(1 << j)][j] = 0;
    }
    for(i = 1; i < (1 << n); i++){
        for(j = 0; j < n; j++){
            if((1 & (i >> j)) == 1){
                for(k = 0; k < n; k++){
                    if((1 & (i >> k)) == 1 && c[k][j] != 0){
                        a[i][j] = min(a[i][j], a[i ^ (1 << j)][k] + c[k][j]);
                    }
                }
            }
        }
    }
    sol = INF;
    i = (1 << n) - 1;
    for(j = 1; j < n; j++){
        if(c[j][0] != 0){
            sol = min(sol, a[i][j] + c[j][0]);
        }
    }
    if(sol == INF){
        fout<<"Nu exista solutie\n";
        return 0;
    }
    fout<< sol <<"\n";
    return 0;
}