#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#define INF (1<<30)
using namespace std;

int N,M,dp[1<<18][19],K,cost[20][20]; vector<int> graf[20];



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

    int i,x,y,j,k;
    for (i=1; i<=M; i++){
        fin >> x >> y;
        fin >> cost[x][y];
        graf[y].push_back(x);
    }

    for (i=0; i<1<<N; i++)
        for (j=0; j<N; j++)
            dp[i][j]=INF;

    dp[0][0]=0;
    for (i=0; i<1<<N; i++)
        for (j=0; j<N; j++){
            if (i&(1<<j)) continue;
            for (k=0; k<graf[j].size(); k++)
                if (i&(1<<graf[j][k]))
                    dp[i][j]=min(dp[i][j],dp[i^(1<<graf[j][k])][graf[j][k]]+cost[graf[j][k]][j]);
        }

    int ans=INF;
    for (i=0; i<graf[0].size(); i++)
        ans=min(ans,dp[((1<<N)-1)^(1<<graf[0][i])][graf[0][i]]+cost[graf[0][i]][0]);

    if (ans==INF)
        fout << "Nu exista solutie\n";
    else
        fout << ans << "\n";

    return 0;
}