#include <fstream>
using namespace std;
int n,m,a[20][20],dp[262144][20];
int main(){
    ifstream f("hamilton.in");
    ofstream g("hamilton.out");
    f>>n>>m;
    for(int i=1;i<=m;++i){
        int x,y,c;
        f>>x>>y>>c;
        a[x][y]=c;
    }
    for(int i=0;i<(1<<n);++i)
        for(int j=0;j<n;++j)
            dp[i][j]=1e9;
    dp[1][0]=0;
    for(int mask=1;mask<(1<<n);++mask){
        if(!(mask&1))continue;
        for(int i=0;i<n;++i){
            if(!(mask&(1<<i)))continue;
            if(dp[mask][i]==1e9)continue;
            for(int j=0;j<n;++j){
                if(mask&(1<<j))continue;
                if(!a[i][j])continue;
                if(dp[mask|(1<<j)][j]>dp[mask][i]+a[i][j])
                    dp[mask|(1<<j)][j]=dp[mask][i]+a[i][j];
            }
        }
    }
    int sol=1e9;
    for(int i=1;i<n;++i)
        if(dp[(1<<n)-1][i]!=1e9&&a[i][0])
            sol=min(sol,dp[(1<<n)-1][i]+a[i][0]);
    if(sol==1e9)g<<"Nu exista solutie";
    else g<<sol;
}