#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

const int INF=1e9;
int n, i, j, m, a, b, c, s;
vector<pair<int, int>> ad[20];
int dp[300000][20], mat[20][20];

int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>a>>b>>c;
        ad[a].push_back({b, c});
        mat[a][b]=c;
    }

    for(s=0;s<(1<<n);s++){
        for(i=0;i<n;i++)
            dp[s][i]=INF;
    }

    dp[1][0]=0;
    for(s=1;s<(1<<n);s++){
        for(i=0;i<n;i++){
            if(s&(1<<i)){
                for(j=0;j<ad[i].size();j++){
                    int vecin=ad[i][j].first;
                    int cost=ad[i][j].second;
                    if((s&(1<<vecin))==0){
                        dp[s+(1<<vecin)][vecin]=min(dp[s+(1<<vecin)][vecin], dp[s][i]+cost);
//                        cout<<i<<" "<<vecin<<" "<<dp[s+(1<<vecin)][vecin]<<'\n';
                    }
                }
            }
        }
    }

    int ans=INF;
    for(i=0;i<n;i++){
        if(mat[i][0]>0)
            ans=min(ans, dp[(1<<n)-1][i]+mat[i][0]);
    }

    if(ans==INF)
        fout<<"Nu exista solutie";
    else
        fout<<ans;


    return 0;
}