#include <iostream>
#include <fstream>
#include <vector>
#define oo 2000000000
using namespace std;
struct str
{
    int nod,cost;
};
vector <str> a[20];
int doi[20];
int dp[1<<18][20];
int n,m;
int suma,sol;
void Ini()
{
    int i,j;
    for(i=0; i<1<<n; i++)
        for(j=0; j<n; j++)
        dp[i][j]=oo;

}
void Read()
{
    ifstream fin("hamilton.in");
    fin>>n>>m;
    int x;
    str w;
    Ini();
    for(int i=1; i<=m; i++)
    {
        fin>>x>>w.nod>>w.cost;
        a[x].push_back(w);
       // dp[i<<x][w.nod]=w.cost;
    }

}
void Pdoi()
{

    doi[0]=1;
    for(int i=1; i<=n; i++)
        doi[i]=doi[i-1]*2;

    suma=doi[n]-1;

}

void Salv()
{
    int k,j,fiu,minim,i;
    dp[1][0]=0;
    for(i=0; i< (1<<n); i++)
        for(j=0; j<n; j++)
        if( i & (1<<j) )
        for(k=0; k<a[j].size(); k++)
        if( i & (1<<j) )
    {
        fiu=a[j][k].nod;
        dp[i][j]=min(dp[i][j],dp[i^(1<<j) ][fiu]+a[j][k].cost);
    }

}
int main()
{

    Read();
    Pdoi();
    Salv();
    int i;
    sol=oo;
    for(i=0; i<a[0].size(); i++)
        {
            sol=min(sol,dp[suma][a[0][i].nod]+a[0][i].cost);
            //cout<<dp[suma][a[0][i].nod]+a[0][i].cost<<" ";
        }
        ofstream fout("hamilton.out");
        if(sol==oo) fout<<"Nu exista solutie";
        else
        fout<<sol;
    return 0;
}