/// circular
/// patratele
#include <bits/stdc++.h>
using namespace std;

#define MOD 666013

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int i, n, m, mat[20][20], j, y, x, c, vf, q[20], dp[1 << 20][20], k;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    fin >> n >> m;
    n--;
    for (i = 1; i <= m; i++)
    {
        fin >> x >> y >> c;
        mat[x][y] = c;
    }
    for (i = 1; i <= (1 << (n + 1)) - 1; i++)
    {
        vf = 0;
        for (j = 0; j <= n; j++)
            dp[i][j] = INT_MAX/2;
        for (j = 0; j <= n; j++)
            if (i & (1 << j))
                q[vf++] = j;
        if (vf == 1)
            dp[i][q[0]] = 0;
        else
        {
            for (j = 0; j < vf; j++)
                for (y = 0; y < vf; y++)
                {
                    if (mat[q[j]][q[y]] && dp[i ^ (1 << q[y])][q[j]] != INT_MAX/2)
                        dp[i][q[y]] = min(dp[i ^ (1 << q[y])][q[j]] + mat[q[j]][q[y]], dp[i][q[y]]);
                }
        }
    }
    int ras = INT_MAX/2;
    for (i = 0; i <= n; i++)
        if(mat[i][0])
            ras = min(ras, dp[(1 << (n + 1)) - 1][i]+mat[i][0]);
    if(ras!=INT_MAX/2)
        fout<<ras;
    else
        fout<<"Nu exista solutie";

    return 0;
}