#include <bits/stdc++.h>

using namespace std;
ifstream in("hamilton.in");
ofstream out("hamilton.out");
vector<int> v[22];
int cost[30][30],dp[262150][22];
#define inf 1e8
int main()
{
    int n,m,i,j,k,ans,x,y;
    in>>n>>m;
    for(i=0;i<n;++i)
        for(j=0;j<n;++j)
            cost[i][j]=inf;
    for(i=1;i<=m;++i){
        in>>x>>y;
        in>>cost[x][y];
        v[y].push_back(x);
    }
    for(i=0;i<(1<<n);++i)
        for(j=0;j<n;++j)
            dp[i][j]=inf;
    dp[1][0]=0;
    for(i=1;i<(1<<n);++i)
        for(j=0;j<n;++j)
            if((i&(1<<j)))
                for(k=0;k<v[j].size();++k)
                    if(i&(1<<v[j][k]))
                        dp[i][j]=min(dp[i][j], dp[i^(1<<j)][v[j][k]]+cost[v[j][k]][j]);

    ans=inf;
    for(i=0;i<v[0].size();++i)
        ans=min(ans,dp[(1<<n)-1][v[0][i]]+cost[v[0][i]][0]);
    if(ans==inf)
        out<<"Nu exista solutie";
    else
        out<<ans;
    return 0;
}