#include <bits/stdc++.h>

using namespace std;

#define N 20

const int INF = 1e9;
int n, dp[(1 << N)][N];

int A[N][N];

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

    int m, x, y, c;
    fin >> n >> m; do {
        fin >> x >> y >> c;
        A[x][y] = c;
    } while(--m);

    dp[1][0] = 0;
    for(int i = 1; i <= n; ++i) dp[1][i] = INF;

    for(int i = 2; i <= (1<<n)-1; i++)
        for(int j = 0; j < n; ++j) {
            if((1 << j) & i) {
                int i_prim = (i ^ (1 << j));
                dp[i][j] = INF;
                for(int k = 0; k < n; ++k) 
                    if(((1 << k) & i) && A[k][j] && dp[i_prim][k] != INF)
                        dp[i][j] = min(dp[i][j], dp[i_prim][k] + A[k][j]);
			}
        }
    
    int rez = INF;
    for(int j = 0; j < n; ++j)
		if(A[j][0] && dp[(1<<n)-1][j] != INF)
        	rez = min(rez, dp[(1<<n)-1][j] + A[j][0]);
	
	if(rez == INF) fout << "Nu exista solutie";
    else fout << rez;
}