#include <bits/stdc++.h>
#define INF 1000000000

using namespace std;

const int nmax=25;
const int vmax=262145;

vector <int> g[nmax];
int cost[nmax][nmax];
int dp[vmax][nmax];

int main()
{
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);
    int n, m;

    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cost[i][j]=INF;
    for(int i=1;i<=m;i++)
    {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        g[y].push_back(x);
        cost[x][y]=c;
    }
    for(int i=0;i<(1<<n);i++)
        for(int j=0;j<n;j++)
            dp[i][j]=INF;
    dp[1][0]=0;
    for(int i=0;i<(1<<n);i++)
        for(int j=0;j<n;j++)
            if(i&(1<<j))
                for(int k=0;k<g[j].size();k++)
                    if(i&(1<<g[j][k]))
                        dp[i][j]=min(dp[i][j], dp[i^(1<<j)][g[j][k]]+cost[g[j][k]][j]);
    int rasp=INF;
    for(int i=0;i<g[0].size();i++)
        rasp=min(rasp, dp[(1<<n)-1][g[0][i]]+cost[g[0][i]][0]);
    if(rasp==INF)
        printf("Nu exista solutie\n");
    else
        printf("%d\n", rasp);

    return 0;
}