#define NMAX 18
#define NRMAX (1<<18)-1
#define INF 0x3f3f3f3f

#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

int n, m;

int dp[NMAX][NRMAX];
int cost[NMAX][NMAX];

void init(){
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++)
            cost[i][j] = INF;
    }
    int nr = (1<<n)-1;
    for(int i=0; i<n; i++){
        for(int j=0; j<=nr; j++)
            dp[i][j]=-1; /// nu am calculat pana acum
    }
}


void citire(){
    f>>n>>m;
    init();
    int x, y, c;
    for(int i=1; i<=m; i++){
        f>>x>>y>>c;
        cost[x][y] = c;
    }
}

int parcurg(int i, int j){ /// drumul minim pana in i parcurgand nodurile din j
    if(dp[i][j]!=-1)
        return dp[i][j];
    if(j == (1<<i)+1)
        return cost[0][i];
    int vmin = INF;
    for(int x=1; x<n; x++)
        if(cost[x][i]!=INF && (j&(1<<x))) /// daca x e in j
            vmin = min(vmin, parcurg(x, j^(1<<i)) + cost[x][i]);
    dp[i][j] = vmin;
    return vmin;
}

void rezolv(){
    int afis = INF;
    int nr = (1<<n)-1;
    for(int i=1; i<n; i++){
        if(cost[i][0] != INF)
            afis = min(afis, parcurg(i, nr) + cost[i][0]);
    }
    if(afis==INF)
        g<<"Nu exista solutie";
    else g<<afis;
}

int main()
{
    citire();
    rezolv();
    return 0;
}