#include <fstream>
#include <vector>
#include <climits>

using namespace std;

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

const int NMAX = 18;
int cost[NMAX + 5][NMAX + 5];
vector <int> graph[NMAX + 5];

const int INF = 1e9;
int dp[1 << 18][NMAX + 2];

int main()
{
    int nodes, edges;
    fin >> nodes >> edges;

    for(int i = 0; i < nodes; i++)
        for(int j = 0; j < nodes; j++)
            cost[i][j] = INF;

    for(int i = 1; i <= edges; i++)
    {
        int node1, node2, cost_node;
        fin >> node1 >> node2 >> cost_node;

        graph[node1].push_back(node2);
        cost[node1][node2] = cost_node;
    }

    for(int i = 0; i < (1 << nodes); i++)
        for(int j = 0; j < nodes; j++)
            dp[i][j] = INF;
    dp[1][0] = 0;

    for(int config = 1; config <= (1 << nodes) - 1; config++)
    {
        for(int curr = 0; curr < nodes; curr++)
        {
            if(dp[config][curr] == INF)
                continue;

            for(auto neigh : graph[curr])
                if((config & (1 << neigh)) == 0)
                dp[config | (1 << neigh)][neigh] = min(dp[config | (1 << neigh)][neigh], dp[config][curr] + cost[curr][neigh]);
        }
    }

    int minim = INT_MAX;

    for(int i = 1; i < nodes; i++)
            if(cost[i][0] != INF and dp[(1 << nodes) - 1][i] != INF)
            minim = min(minim, dp[(1 << nodes) - 1][i] + cost[i][0]);

    if(minim == INT_MAX)
        fout << "Nu exista solutie";
    else
    fout << minim;

    fin.close();
    fout.close();
    return 0;
}