#include <bits/stdc++.h>

using namespace std;

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

const int INF=1e9+2,mc=(1<<18)+25;

int a[25][25],n,m,x,y,c,dp[mc][25];
int main() {
    int n,m;
    fin>>n>>m;
    for (int i=0;i<n;i++) {
        for (int j=0;j<n;j++) {
            a[i][j]=INF;
        }
    }
    for (int i=1;i<(1<<18);i++) {
        for (int j=0;j<n;j++) {
            dp[i][j]=INF;
        }
    }
    dp[1][0]=0;// de la primul nod pornim cu cost 0
    while (m--) {
        fin>>x>>y>>c;
        a[x][y]=min(a[x][y],c);
    }
    for (int i=1;i<(1<<n);i++) {
        for (int j=0;j<n;j++) {
            if (i&(1<<j)) {
                for (int k=0;k<n;k++) {
                    if ((i&(1<<k))==0) {
                        dp[i|(1<<k)][k]=min(dp[i|(1<<k)][k],dp[i][j]+a[j][k]);
                    }
                }
            }
        }
    }
    int rez=INF;
    for (int i=0;i<n;i++) rez=min(rez,dp[(1<<n)-1][i]+a[i][0]);
    if (rez==INF) fout<<"Nu exista solutie";
    else fout<<rez;
    return 0;
}