#include<fstream>
#include<vector>
#define INF 2*0x3F3F3F3F
std::ifstream cin("hamilton.in");
std::ofstream cout("hamilton.out");
using namespace std;
int n ,m ,adj[20][20] ,u ,v ,cost;
vector<int>g[20];
int main () {
    cin>>n>>m;
    int masca=(1<<n);
    vector<vector<int>>dp(masca,vector<int>(n,INF));
    dp[1][0]=0;
    while (m--) {
    cin>>u>>v>>cost;
    adj[v][u]=cost;
    g[u].push_back(v);
    }
    for (int mask=3 ;mask<masca ;mask+=2)
        for (int i=1 ;i<n ;i++)
            if (mask&(1<<i))
                for (auto kid:g[i])
                    dp[mask][i]=min(dp[mask][i],dp[mask^(1<<i)][kid]+adj[kid][i]);
    int ans=INF;
    for (int i=1 ;i<n ;i++)
        ans=min(ans,dp[masca-1][i]+adj[i][0]);
        if (ans==INF) cout<<"Nu exista solutie";
        else
    cout<<ans;
return 0;
}