#include <iostream>
#include <fstream>
#include <vector>
#define lmax 1<<20
#define lmic 20
#define infinit 1<<25

using namespace std;

int c[lmax][lmic];
int cost[lmic][lmic];
vector<int>v[lmic];
int n,m;
void infiniteaza()
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cost[i][j]=infinit;
        }
    }
    for(int i=0;i<(1<<n);i++)
    {
        for(int j=0;j<n;j++)
        {
            c[i][j]=infinit;
        }
    }
    c[1][0]=0;
}

void parcurgere()
{
    for(int i=0;i<(1<<n);i++)
    {
        for(int j=0;j<n;j++)
        {
            if(i&(1<<j))
            {
                for(int k=0;k<v[j].size();k++)
                {
                    if(i &(1<<v[j][k]))
                    {
                            c[i][j]=min(c[i][j],c[i^(1<<j)][v[j][k]]+cost[v[j][k]][j]);
                    }
                }
            }
        }
    }
}
int verificare()
{
    int sol=infinit;
    for( int i=0;i<v[0].size();i++)
    {
        sol=min(sol,c[(1<<n)-1][v[0][i]]+cost[v[0][i]][0]);
    }
    return sol;
}
int main()
{
    int a,b;
    ifstream f("hamilton.in");
    ofstream g("hamilton.out");
    f>>n>>m;
    infiniteaza();
    for(int i=1;i<=m;i++)
    {
        f>>a>>b;
        v[b].push_back(a);
        f>>cost[a][b];
    }
    parcurgere();
    int s=verificare();
    if(s==infinit)
    {
        g<<"Nu exista solutie";
        return 0;
    }
    g<<s;
    return 1;
}