#include <bits/stdc++.h>

#define NMax 18
#define INF (1 << 30) - 1
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");

int n,m,x,y,c;
int a[NMax][NMax];
int best[(1 << 18)][NMax];
vector<int> G[NMax];
int main()
{
  //  g << 1.0*(sizeof(best))/1024/1024 << '\n';
    f >> n >> m;
    for(int i = 0; i <= n; ++i){
        for(int j = 0; j <= n; ++j){
            if(i != j)
                a[i][j] = INF;
        }
    }
    for(int i = 1; i <= m; ++i){
        f >> x >> y >> c;
        G[x].push_back(y);
        a[x][y] = c;
    }
    for(int mask = 0; mask <= (1 << n); ++ mask)
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j)
                best[mask][i] = INF;

    best[(1 << 0)][0] = 0;
    for(int mask = 0; mask <= (1 << n); ++ mask){

        for(int i = 0; i < n; ++i){

            for(int w = 0; w < G[i].size(); ++w){
                int j = G[i][w];
                if(!(mask & (1 << j))){
                    best[mask|(1 << j)][j] = min(best[mask|(1 << j)][j],best[mask][i] + a[i][j]);
                }
            }
        }
    }

    int ans = INF;
    for(int i = 0; i < n; ++i){
        ans = min(ans,best[(1 << n) - 1][i] + a[i][0]);
    }
    if(ans == INF)
        g << "Nu exista solutie" << '\n';
    else
        g << ans << '\n';
    return 0;
}