#include <bits/stdc++.h>
#define INF 2e9
using namespace std;

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

int n, m, a[20][20], N;
int dp[18][1 << 18]; //dp[i][masca] = costul minim al drumului de la 0 la i, trecand prin
                     //nodurile marcate cu 1 in reprezentarea in baza 2 a lui masca
void Test_Case()
{   
    int i, j, x, y, c, masca, sol;
    fin >> n >> m;
    N = (1 << n);
    for (i = 1; i <= m; i++)
    {
        fin >> x >> y >> c;
        a[x][y] = c;      
    }

    for (i = 0; i < n; i++)
        for (j = 0; j < N; j++)
            dp[i][j] = INF;

    dp[0][1] = 0; /// initial ne aflam in nodul 0 (este setat doar bitul 0 in masca)
    for (masca = 3; masca < N; masca += 2) // din 2 in 2 pentru ca masca sa aiba mereu bitul 0 setat
        for (i = 0; i < n; i++)
            if (masca & (1 << i))
            {
                x = masca - (1 << i);
                for (j = 0; j < n; j++)
                    if (x & (1 << j) and a[j][i])
                        dp[i][masca] = min(dp[i][masca], dp[j][x] + a[j][i]);
            }

    sol = INF;
    for (i = 1; i < n; i++)
        if (a[i][0])
            sol = min(sol, dp[i][N - 1] + a[i][0]);

    if (sol == INF)
        fout << "Nu exista solutie\n";
    else fout << sol << "\n";

}

int main()
{
    int t;
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    t = 1;
    while (t--)
        Test_Case();

    return 0;
}