#include <bits/stdc++.h>

using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");

const int N = 18, INF32 = 0x3f3f3f3f;
int n, m, x, y, cost, dp[N][1 << N], c[N][N], ans = INF32;

int main(){
    f >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            c[i][j] = INF32;

    for(int i = 0; i < m; i++){
        f >> x >> y >> cost;
        c[x][y] = cost;
    }

    f.close();
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 1 << n; j++)
            dp[i][j] = INF32;

        dp[i][1 << i] = 0;
    }

    for(int j = 1; j < 1 << n; j++){
        for(int i = 0; i < n; i++){
            if(j & (1 << i)){
                for(int k = 0; k < n; k++){
                    if(j & (1 << k) || c[i][k] == INF32)
                        continue;

                    dp[k][j + (1 << k)] = min(dp[k][j + (1 << k)], dp[i][j] + c[i][k]);
                }
            }
        }
    }

    for(int i = 1; i < n; i++)
        ans = min(ans, dp[i][(1 << n) - 1] + c[i][0]); // + c[i][0] pt. ca e ciclu

    if(ans == INF32)
        g << "Nu exista solutie";
    else
        g << ans;

    g.close();
}