#include <fstream>
#include <vector>

using namespace std;

const int max_n = 18;
const int max_st = (1<<18);
const int inf = 100000000;

vector<int> gf[max_n];
int n, m;
int dp[max_st][max_n];
int cost[max_n][max_n];
int sol;
ifstream f("hamilton.in");
ofstream g("hamilton.out");

void citeste(){

    f>>n>>m;

    for(int i=0; i < n; ++i)
        for(int j=0; j < n; ++j) cost[i][j] = inf;

    for(int i=1; i<=m; ++i){
        int x,y;
        f>>x>>y;
        gf[y].push_back(x);
        f>>cost[x][y];
    }

}

int minim(int x, int y){

    if (x > y) return y;
    return x;

}


void hamilton(){

    for(int i=0; i<=(1<<n)-1; ++i)
        for(int j=0; j<=n-1; ++j) dp[i][j] = inf;


    dp[1][0] = 0;

    for(int i = 0; i <= (1<<n)-1; ++i){
        for(int j = 0; j <= n-1; ++j){
            if (( i & (1 << j)) != 0){
                for(unsigned w = 0; w < gf[j].size(); ++w){
                    int vecin = gf[j][w];
                    if ((i & ( 1 << vecin)))
                        dp[i][j] = minim(dp[i][j], dp[i ^ (1<<j)][vecin] + cost[vecin][j]);
                }
            }
        }
    }

    sol = inf;

    for(unsigned i = 0; i < gf[0].size(); ++i){
        int vecin = gf[0][i];
        sol = minim (sol, dp[(1<<n)-1][vecin] + cost[vecin][0]);
    }

}

void scrie(){

/*
    for(int i = 0 ; i < 1<<n; ++i){
        for(int j = 0; j < n; ++j)
            g<<dp[i][j]<<" ";
        g<<"\n";
    }

*/
    if (sol == inf) g<<"Nu exista solutie"<<"\n";
    else g<<sol<<"\n";

}

int main(){

    citeste();
    hamilton();
    scrie();

    f.close();
    g.close();

    return 0;

}