#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstring>
#include <climits>
#include <unordered_map>
#define NMAX 300003
using namespace std;

int n, m;
int dp[NMAX][20];

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

unordered_map<int, int>  graf[20];//graful de costuri

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        int cost;
        fin >> x >> y >> cost;

        graf[x].insert({ y,cost });
    }
    //ar fi bine sa pun INT_MAX peste tot in dp
    for (int cod = 1; cod < (1 << n); cod += 2)
    {
        for (int last = 0; last < n; last++)
        {
            dp[cod][last] = INT_MAX;
        }
    }

    dp[1][0] = 0;
    for (int cod = 1; cod < (1 << n); cod += 2)
    {
        for (int last = 0; last < n; last++)
        {
            if (dp[cod][last] != INT_MAX)
            {
                //am elementul asta in cod
                for (auto elem : graf[last])
                {
                    int urm = elem.first;//am venit de aici
                    if (((cod >> urm) & 1) == 0)
                    {
                        // e prima data in codificarea asta cand dau in elem asta
                        int p2 = (1 << urm);
                        dp[cod + p2][urm] = min(dp[cod + p2][urm], dp[cod][last] + elem.second);
                    }
                }
            }
        }
    }
    //imi iau minimul de la final
    int minim = INT_MAX;
    int p2 = (1 << n) - 1;
    for (int i = 1; i < n; i++)
    {
        auto itr = graf[i].find(0);
        if (itr != graf[i].end() && dp[p2][i] != INT_MAX)
        {
            minim = min(minim, dp[p2][i] + itr->second);
        }

    }
    if (minim != INT_MAX)
    {
        fout << minim;
        return 0;
    }
    fout << "Nu exista solutie\n";
    return 0;
}