#include <fstream>
#include <iostream>
#include <vector>
#define nmax 19

using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");

int n, m, cost[nmax][nmax];
vector<int> gf[nmax];
int dp[(1<<nmax)][nmax];

void citeste(){

    f >> n >> m;
    for(int i=1; i<=m; i++){
        int x, y, c;
        f >> x >> y >> c;
        gf[y].push_back(x);//fac invers graful din cauza ordinii bitiilor
        cost[x][y] = c;
    }

}

void rezolva(){

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

    dp[1][0] = 0;

    for(int i=0; i<(1<<n); i++){
        for(int j=0; j<n; j++){
            //daca pozitia j din i e 1
            if (i & (1<<j) ){
                for(int w=0; w<gf[j].size(); w++){
                    int vc = gf[j][w];
                    //daca pe pozitia vc din i e 1
                    if (i & (1<<vc) ){
                        dp[i][j] = min(dp[i][j], dp[i^(1<<j)][vc] + cost[vc][j]);
                    }
                }
            }
        }
    }

    int rez = (1<<30);

    for(int i=0; i<gf[0].size(); i++){
        int vc = gf[0][i];
        rez = min(rez, dp[(1<<n)-1][vc] + cost[vc][0]);
    }

    if (rez == (1<<30) ) g << "Nu exista solutie" << "\n";
    else g << rez << "\n";

}

int main(){

    citeste();
    rezolva();

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

    return 0;

}