#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("hamilton.in");
ofstream cout("hamilton.out");
int a[20][20];
int n,p;
int mi=20000000;
vector<vector<int>>m(20);
vector<vector<int>> dp((1<<18)+1,vector<int>(20,20000000));
bool ok(int stare, int x) {
    return !((stare>>x)&1);
}
void fct(int i,int stare) {
    for (auto x:m[i]) {
        if (stare==(1<<n)-1&&x==0)mi=min(mi,dp[stare][i]+a[i][x]);
        if (ok(stare,x)) {
            dp[stare|(1<<x)][x]=min(dp[stare|(1<<x)][x],dp[stare][i]+a[i][x]);
            //cout<<"sunt in starea "<<(stare|(1<<x))<<" se termina in "<<x<<" are val "<<dp[stare|(1<<x)][x]<<endl;
            fct(x,stare|(1<<x));
        }
    }
}
int main() {
    cin>>n>>p;
    for (int i=0;i<p;i++) {
        int x,y,c;
        cin>>x>>y>>c;
        a[x][y]=c;
        m[x].push_back(y);
    }
    dp[1][0]=0;
    for (auto x:m[0]) {
        dp[1|(1<<x)][x]=min(dp[1|(1<<x)][x],a[0][x]);
        //cout<<"sunt in starea "<<(1|(1<<x))<<" se termina in "<<x<<" are val "<<dp[1|(1<<x)][x]<<endl;
        fct(x,1|(1<<x));
    }
    if (mi!=20000000)cout<<mi;
    else cout<<"Nu exista solutie";
}