#include <bits/stdc++.h>
using namespace std;
ifstream in("hamilton.in");
ofstream out("hamilton.out");
const int inf=100000000;
vector<int> rev[20];
int dp[20][(1<<18)+3];
int cost[20][20];
int n,m,x,y;
int main()
{
    ios_base::sync_with_stdio(false);
    in.tie(0),out.tie(0);
    in>>n>>m;
    for(int i=0;i<n;++i)
    for(int j=0;j<n;++j)
        cost[i][j]=inf;
    for(int i=1;i<=m;++i)
        in>>x>>y,
        rev[y].push_back(x),
        in>>cost[x][y];
    for(int i=0;i<n;++i)
    for(int j=0;j<(1<<n);++j)
        dp[i][j]=inf;
    dp[0][1]=0;
    for(int mask=2;mask<(1<<n);++mask)
    for(int i=0;i<n;++i) if(mask&(1<<i))
    for(int x=0;x<rev[i].size();++x) if(mask&(1<<rev[i][x]))
        dp[i][mask]=min(dp[i][mask],dp[rev[i][x]][mask^(1<<i)]+cost[rev[i][x]][i]);
    int ans=inf;
    for(int i=0;i<rev[0].size();++i)
        ans=min(ans,dp[rev[0][i]][(1<<n)-1]+cost[rev[0][i]][0]);
    if(ans==inf)
        out<<"Nu exista solutie"<<'\n';
    else out<<ans<<'\n';
    return 0;
}