#include <bits/stdc++.h>
#define INF 20000000 //20 mil
using namespace std;

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

int cost[20][20];
int C[262145][19];
int n,m,rez;

int pow(int baza,int exp)
{
    int sol=1;
    for(int i=1;i<=exp;i++)
        sol*=baza;
    return sol;
}
int calc(int j,int k)
{
    ///cazul simplu mai avem doar 2 puncte
    if(C[j][k]!=0)
        return C[j][k];
    if(pow(2,k)+1== j && cost[0][k]!=0)
    {
        C[j][k]=cost[0][k];
        return cost[0][k];
    }
    int mi=INF;
    for(int v=1;v< n;v++)
        if(cost[v][k]!=0 && /*bitul v din j */ (j>>v)%2    == 1 )
        {
            if(C[j-pow(2,k)][v]==0)
                C[j-pow(2,k)][v]= calc(j-pow(2,k),v);
            mi = min(   C[j-pow(2,k)][v]+cost[v][k], mi);
        }
    C[j][k]=mi;
    return mi;
}

int main()
{
    ///incepem inscrierea nodurilor de la 0
    int x,y,c;
    f>>n>>m;
    while(m--)
    {
        f>>x>>y>>c;
        cost[x][y]=c;
    }
    rez=INF;
    for(int k=1; k< n; k++)
        if(cost[k][0]!=0)
            rez=min( rez, calc(pow(2,n)-1,k) + cost[k][0]);
    ///daca costul depaseste INF => nu avem solutie
    if(rez==0 || rez>= INF)
        g<<"Nu exista solutie";
    else g<<rez;
}