#include <bits/stdc++.h>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

const int inf = 1e9 + 2, maxc = (1 << 18) + 20;

int cost[20][20], dp[maxc][20];

int main()
{
    int n, m;
    fin>>n>>m;
    for(int i=1; i<(1<<n); i++)
        for(int j=0; j<n; j++)
            dp[i][j]=inf;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cost[i][j]=inf;
    while (m--){
        int x, y, c;
        fin>>x>>y>>c;
        cost[x][y]=min(cost[x][y], c);
    }
    dp[1][0]=0;
    for(int i=1; i<(1<<n); i++)
        for(int j=0; j<n; j++)
            if((i&(1<<j))!=0)
                for(int k=0; k<n; k++)
                    if((i&(1<<k))==0)
                        dp[i|(1<<k)][k]=min(dp[i|(1<<k)][k], dp[i][j]+cost[j][k]);

    int out=inf;
    for(int j=0; j<n; j++)
        out=min(out, dp[(1<<n)-1][j]+cost[j][0]);
    if(out==inf) fout<<"Nu exista solutie";
    else fout<<out;
    return 0;
}