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

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

int n, m;
int cost[20][20], dp[(1 << 18)][19];
vector<int> vecini[18];

int main()
{
    fin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        cost[x][y] = c;
        vecini[x].push_back(y);
    }
    memset(dp, 0x3f3f3f3f, sizeof dp);
    dp[1][0] = 0;
    // Luam toate configuratiile posibile
    for (int i = 1; i < (1 << n); i++)
    {
        for (int j = 0; j < n; j++)
        {
            // Putem pleca din nodul j pentru ca este prezent in configuratie
            if (i & (1 << j))
            {
                for (int k = 0; k < vecini[j].size(); k++)
                {
                    int vecin = vecini[j][k];
                    // Vecinul nu e inclus in configuratie, deci il putem adauga la configuratie si sa calculam
                    if ((i & (1 << vecin)) == 0)
                        dp[i + (1 << vecin)][vecin] = min(dp[i + (1 << vecin)][vecin], dp[i][j] + cost[j][vecin]);
                }
            }
        }
    }
    int ans = 0x3f3f3f3f;
    // Unim lanturile cu startul pentru a forma ciclul (startul e nodul 0)
    for (int i = 1; i < n; i++)
    {
        if (cost[i][0] != 0)
            ans = min(ans, dp[(1 << n) - 1][i] + cost[i][0]);
    }
    if (ans == 0x3f3f3f3f)
        fout << "Nu exista solutie\n";
    else
        fout << ans << "\n";
    return 0;
}