#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

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

const int LMAX = 20;
const int INF = 0x3F3F3F3F;

int a[LMAX][LMAX];

int main() {
    int n, m, x, y, c;
    fin>>n>>m;
    while (m--) {
        fin>>x>>y>>c;
        a[x][y] = c;
    }
    vector<vector<int>> dp((1<<n), vector<int>(n, INF)); //dp[i][j] --> costul minim al drumului care se termina in nodul i cu drumul j
    int i, j, mask;
    dp[1][0] = 0;
    for (mask = 2; mask < (1<<n); mask++) {
        for (i = 0; i < n; i++) {
            if ((mask&(1<<i))) {
                for (j = 0; j < n; j++) {
                    if (i != j && (mask&(1<<j)) && a[j][i]) { //de unde vine si exista drumul
                        dp[mask][i] = min(dp[mask][i], dp[(mask^(1<<i))][j] + a[j][i]);
                    }
                }
            }
        }
    }
    mask--;
    int maxi = INF;
    for (i = 0; i < n; i++) {
        if (a[i][0]) maxi = min(maxi, dp[mask][i] + a[i][0]);
    }
    if (maxi == INF) fout<<"Nu exista solutie";
    else fout<<maxi;




    fin.close();
    fout.close();
    return 0;
}