#include <bits/stdc++.h>

using namespace std;

const int nmax=18;
const int mmax=1<<18;

int n,m;
int x,y,cost;

int adj[mmax][nmax];
int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    scanf("%d %d",&n,&m);

    vector <vector<int>> dp(mmax,vector<int>(nmax,1e9));
    for(int i=1;i<=m;i++){
        scanf("%d %d %d",&x,&y,&cost);
        adj[x][y]=cost;
    }
    dp[1][0]=0;

    for(int mask=1;mask<(1<<n);mask++){
        //parcurgem nodurile care sunt in masca
        for(int node=0;node < n;node++){
            if(mask&(1<<node)){
                ///daca nodul este in mask
                for(int neigh=0;neigh < n;neigh++){
                    if(mask & (1<<neigh) || adj[node][neigh]==0)
                        continue;

                    int new_mask=mask+(1<<neigh);
//                    cout<<"mask="<<mask<<", node="<<node<<", neigh="<<neigh<<"\n";
//                    cout<<"dp="<<dp[new_mask][neigh]<<"\n";
                    dp[new_mask][neigh]=min(dp[new_mask][neigh],dp[mask][node]+adj[node][neigh]);
//                    cout<<"new_dp="<<dp[new_mask][neigh]<<"\n\n";
                }
            }
        }
    }
    int ans=1e9;
    for(int node=0;node<n;node++){
        if(adj[node][0])
            ans=min(ans,dp[(1<<n)-1][node]+adj[node][0]);
    }

    if(ans>=1e9){
        printf("Nu exista solutie");
        return 0;
    }

    printf("%d",ans);




    return 0;
}