#include <bits/stdc++.h>

using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int mare = 1e9+7;

int n, m, c[20][20], dp[263000][19];

int main()
{
    fin>>n>>m;

    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            c[i][j] = mare;

    for(int masca = 0; masca <= (1<<n) - 1; ++masca)
    {
        for(int i = 0; i < n; ++i)
            dp[masca][i] = mare;
    }

    for(int i = 1; i <= m; ++i)
    {
        int x, y, cost;
        fin>>x>>y>>cost;
        c[x][y] = cost;
    }
    dp[1][0] = 0;

    int tot = (1<<n) - 1;
    for(int masca = 2; masca <= tot; ++masca)
    {
        for(int nod = 0; (1<<nod) <= masca; ++nod)
        {
            if(!(masca & (1<<nod)))
                continue;

            for(int ant = 0; (1<<ant) <= masca; ++ant)
            {
                if(!(masca & (1<<ant)))
                    continue;
                dp[masca][nod] = min(dp[masca ^ (1<<nod)][ant] + c[ant][nod], dp[masca][nod]);
            }

        }
    }
    int rez = mare;
    for(int i = 0; i < n; ++i)
    {
        rez = min(dp[tot][i] + c[i][0], rez);
    }
    if(rez == mare)
        fout<<"Nu exista solutie";
    else
        fout<<rez;







    return 0;
}