#include <fstream>
#include <vector>
using namespace std;

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

vector <int> v[18];
int c[18][18], dp[1<<18][18]; //dp[i][j] = costul minim unui lant de la 0 la j, folosind nodurile din starea i

int main()
{
    int n, i, j, k, m, x;
    fin >> n >> m;
    for (i = 0; i<n; i++)
        for (j = 0; j<n; j++)
            c[i][j] = 1<<27;
    for (i = 1; i<=m; i++)
    {
        fin >> j >> k >> x;
        c[j][k] = x;
        v[k].push_back(j);
    }
    for (i = 1; i<(1<<n); i++)
        for (j = 0; j<n; j++)
            dp[i][j] = 1<<27;
    dp[1][0] = 0;
    for (i = 1; i<(1<<n); i++)
        for (j = 0; j<n; j++)
            if (i & (1<<j))
                for (k = 0; k<v[j].size(); k++)
                    if (i & (1<<v[j][k]))
                        dp[i][j] = min(dp[i][j], dp[i ^ (1<<j)][v[j][k]] + c[v[j][k]][j]);
    int rasp = 1<<27;
    for (i = 0; i<v[0].size(); i++)
        rasp = min(rasp, dp[(1<<n)-1][v[0][i]] + c[v[0][i]][0]);
    if (rasp == (1<<27))
        fout << "Nu exista solutie";
    else
        fout << rasp;
    return 0;
}