#include <fstream>
using namespace std;

ifstream cin("hamilton.in");
ofstream cout("hamilton.out");

int n,m,ans,NMAX,g[18][18],a[1<<18][18];

void citire()
{
    cin>>n>>m;
    NMAX=1<<n;
    for(int i=0; i<NMAX; i++)
        for(int j=0; j<n; j++)
            a[i][j]=(1<<30);
    int x,y,c;
    for(int i=0; i<m; i++)
    {
        cin>>x>>y>>c;
        g[x][y]=c;
    }
}
void dp()
{
    a[1][0]=0;//lant ce se termina in nodul j=0 si are in configuratie doar nodul 0
    for(int nr=1;nr<NMAX;nr++)
        for(int nod=0;nod<n;nod++)
        if(nr& (1<<nod))//nodul exista in lant
    {
        for(int j=0;j<n;j++)//caut nodul urmator
        {
            if(g[nod][j] && !(nr & (1<<j)))//daca exista arc nod-j si nodul j nu e folosit in lantul codificat cu nr
            {
                a[nr^(1<<j)][j]=min(a[nr^(1<<j)][j],a[nr][nod]+g[nod][j]);
            }
        }
    }
    ans=INT_MAX;
    for(int i=0; i<n; i++)
        if(g[i][0])//daca exista arc de la ultimul nod la primul, pot forma ciclu
            ans=min(ans,a[NMAX-1][i]+g[i][0]);
}
int main()
{
    citire();
    dp();
    if(ans==INT_MAX)
        cout<<"Nu exista solutie";
    else
        cout<<ans;
    return 0;
}