#include <iostream>
#include <fstream>
#include <vector>
#define MAX 999999999
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

vector <int> Nicu[20];
int cost[20][20],Plicu[20][262150],n,m;

void init()
{

    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++)
            Plicu[i][j]=MAX;
    }
}
void citire()
{
    fin>>n>>m;
    int x,y;
    init();
    for(int i=1; i<=m; i++)
    {
        fin>>x>>y;
        Nicu[y].push_back(x);
        fin>>cost[x][y];
    }

}
void rez()
{
    for(int j=0; j<(1<<n); j++)
        for(int i=0; i<n; i++)
        {
            if(j&(1<<i))
            {
                for(auto &v:Nicu[i])
                {
                    int mini=Plicu[i][j];
                    if((1<<v)&j)
                    {
                        if(mini>Plicu[v][j^(1<<i)]+cost[v][i])
                            mini=Plicu[v][j^(1<<i)]+cost[v][i];
                    }
                    Plicu[i][j]=mini;
                }
            }
        }
}
void rasp()
{
    int rez=MAX;
    for(auto &v:Nicu[0])
        rez=min(rez,Plicu[v][(1<<n)-1]+cost[v][0]);
    if(rez==MAX)
        fout<<"Nu exista solutie";
    else
        fout<<rez;
}
int main()
{
    citire();
    Plicu[0][1]=0;
    rez();
    rasp();
    return 0;
}