#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)][18];

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;
        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 j = 0; j < n; ++j){

                for(int start = 0; start < n; ++ start){
                    if(!(mask & (1 << j)) && a[i][j] != INF && i != 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;
}