#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define MAX 999999999
std :: ifstream f("hamilton.in");
std :: ofstream g("hamilton.out");

using namespace std;

vector<int>graph[20];

int n, m, cost[20][20], dp[20][262150],from,to,rez=MAX;

int main() {
    f >> n >> m;
    for (int i=0; i<=19; i++)
    {
        for (int j=0; j<=19; j++)
            cost[i][j]=MAX;
    }
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<(1<<n); j++)
            dp[i][j]=MAX;
    }
    for (int i=1; i<=m; i++)
    {
        f >> from >> to;
        graph[to].push_back(from);
        f >> cost[from][to];
    }
    dp[0][1]=0;
    for (int masca=0; masca < (1<<n); masca++)
    {
        for (int nod=0; nod<n; nod++)
        {
            if (masca & (1<<nod))
            {
                for (auto &v:graph[nod])
                {
                    int mini=dp[nod][masca];
                    if ((1<<v)&masca)
                    {
                        if (dp[v][masca ^ (1<<nod)]+cost[v][nod]<mini)
                            mini=dp[v][masca^(1<<nod)]+cost[v][nod];
                    }
                    dp[nod][masca]=mini;
                }
            }
        }
    }

    for (auto &v:graph[0])
    {
        rez=min(rez,dp[v][(1<<n)-1]+cost[v][0]);
    }
    if (rez==MAX)
    {
        g << "Nu exista solutie";
    }
    else
        g << rez;
    return 0;
}