#include <bits/stdc++.h>
using namespace std;
const string txt="hamilton";

ifstream fin (txt+".in");
ofstream fout(txt+".out");
#pragma GCC optimize("O3,unroll-loops")
#define cin fin
#define cout fout
#define pii pair<int,int>
#define pb push_back
const int inf=1e9;;
typedef  long long int ll;

const int nmax=19;
int graf[nmax][nmax];
int n,m;
int dp[1<<nmax+1][nmax];
vector<int> startnode[1<<nmax+1][nmax];

inline  void read() {
    cin>>n>>m;
    for (int i=0;i<nmax;i++)
        for (int j=0;j<nmax;j++)
            graf[i][j]=inf;

    while (m--) {
        int n1,n2,c;
        cin>>n1>>n2>>c;
        graf[n1][n2]=c;
    }
}

int main() {
    read();
    for (int mask=1;mask<(1<<n);mask++) {
        fill(dp[mask],dp[mask]+nmax,inf);
        if (__builtin_popcount(mask)==1) {
            dp[mask][__builtin_ctz(mask)]=0;
            startnode[mask][__builtin_ctz(mask)].pb(__builtin_ctz(mask));
        }
        else {
            for (int i=0;i<n;i++) {
                if ((1<<i)&mask) {
                    for (int j=0;j<n;j++) {
                        if (((1<<j)&mask)&&i!=j) {
                            if (dp[mask][i]>dp[mask^(1<<i)][j]+graf[j][i]) {
                                dp[mask][i]=dp[mask^(1<<i)][j]+graf[j][i];
                                vector<int>().swap(startnode[mask][i]);
                            }
                            if (dp[mask][i]==dp[mask^(1<<i)][j]+graf[j][i]) {
                                for (auto nos:startnode[mask^(1<<i)][j])
                                    startnode[mask][i].pb(nos);
                            }
                        }
                    }
                }
            }
        }
    }
    //dp[1<<n] are ciclu
    int sol=inf;
    for (int i=0;i<n;i++) {
        for (auto nodstart:startnode[(1<<n)-1][i])
            sol=min(sol,dp[(1<<n)-1][i]+graf[i][nodstart]);
    }
    if (sol!=inf)
    cout<<sol;
    else cout<<"Nu exista solutie";
}