#include <fstream>
#include <vector>
 
#define NMax 20
 
using namespace std;
 
ifstream f("hamilton.in");
ofstream g("hamilton.out");
 
int nodes, edges, n1, n2, c, mark[NMax], dmin = 1000000000;
vector<int> G[NMax], cost[NMax];
 
void dfs(int node, int touchedNodes, int mcost)
{
    mark[node] = true;
 
    for (vector<int>::iterator itg = G[node].begin(), itc = cost[node].begin(); itg != G[node].end(); itg++, itc++) {
 
        if (!mark[*itg] && mcost + *itc <= dmin)
            dfs(*itg, touchedNodes + 1, mcost + *itc);
 
        if (*itg == 0 && touchedNodes == nodes && mcost + *itc < dmin)
            dmin = mcost + *itc;
 
    }
 
    mark[node] = false;
}
 
int main()
{
    f >> nodes >> edges;
 
    for (int i = 1; i <= edges; i++) {
        f >> n1 >> n2 >> c;
 
        G[n1].push_back(n2);
        cost[n1].push_back(c);
    }
 
    dfs(0, 1, 0);
    if (dmin == 1000000000)
        g << "Nu exista solutie";
    else
        g << dmin;
 
    return 0;
}