#include <fstream>
#include <math.h>
#include <string.h>
using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");

const int INF = 1069531071;
int dp[20][262200];
int cost[20][20];
int n, m;

void init()
{
    for(int i = 0; i<n; i++)
    {
        for(int j = 0; j<(1<<n); j++)
        {
            dp[i][j] = -1;
        }
    }
    for(int i = 0; i<n; ++i)
        for(int j = 0; j<n; ++j)
            cost[i][j] = INF;
    dp[0][1] = 0;
}

void citire()
{
    f>>n>>m;
    init();
    int x, y, c;
    for(int i = 0; i<m; ++i)
    {
        f>>x>>y>>c;
        cost[x][y] = c;
    }
}

int calcCostMin(int i, int j)
{
    if(dp[i][j] == -1) {
        dp[i][j] = INF;
        for(int x = 0; x<n; ++x)
        {
            if(cost[x][i] != INF && ((1<<x) & j) != 0)
                dp[i][j] = min(dp[i][j], calcCostMin(x, (j^(1<<i))) + cost[x][i]);
        }
    }
    return dp[i][j];
}

void solve()
{
    int minim = INF;
    for(int i = 1; i<n; ++i)
    {
        if(cost[i][0] != INF)
        minim = min(minim, calcCostMin(i, (1<<n)-1) + cost[i][0]);
    }
    if(minim != INF)
        g<<minim;
    else
        g<<"Nu exista solutie";
}

int main()
{
    citire();
    solve();
    return 0;
}