#include <bits/stdc++.h>

using namespace std;
ifstream in("hamilton.in");
ofstream out("hamilton.out");
int n, m, inter[18][18], cont[18], c[18][18], dp[300000][18];

int main()
{
    in>>n>>m;
    for(int i=1;i<=m;i++){
        int x, y, z;
        in>>x>>y>>z;
        cont[y]++;
        inter[y][cont[y]]=x;
        c[x][y]=z;
    }
    for(int i=0;i<(1<<n);i++)
        for(j=0;j<n;j++)
            dp[i][j]=1e9;
    dp[1][0]=0;
    for(int subm=3; subm<=(1<<n); subm+=2)
        for(int i=1;i<n;i++)
            if(subm &(1<<i))
                for(j=1; j<=cont[i]; j++)
                    dp[subm][i]=min(dp[subm][i], dp[subm^(1<<i)][inter[i][j]]+c[inter[i][j]][i]);
    int sol=1e9;
    for(int i=1;i<n;i++)
        sol=min(sol, dp[(1<<n)-1][i]+cost[i][0]);
    if(sol==1e9)
        out<<"Nu exista solutie";
    else out<<sol;
    }