#include <bits/stdc++.h>
#define maxim 999999999
using namespace std;
int n,m,dp[20][262150],cost[20][20];
ifstream f("hamilton.in");
ofstream g("hamilton.out");

void rezolvare()
{
    for(int j=0; j<(1<<n); j++)
        for(int i=0; i<n; i++)
            if(j&(1<<i))
                for(int x=0;x<n;x++)
                    if((j&(1<<x))&&cost[i][x]!=maxim)
                        if(dp[x][j^(1<<i)]+cost[x][i]<dp[i][j])
                            dp[i][j]=dp[x][j^(1<<i)]+cost[x][i];
}

void init()
{
    for(int i=0;i<=19;i++)
        for(int j=0;j<=19;j++)
            cost[i][j]=maxim;
    for(int i=0;i<19;i++)
        for(int j=0;j<(1<<18);j++)
            dp[i][j]=maxim;
}

void citire()
{
    int x,y;
    for(int i=0; i<m; i++)
    {
        f>>x>>y;
        f>>cost[x][y];
    }
}

void rez()
{
    int mi=maxim,last=(1<<n)-1;
    for(int i=0;i<=n;i++)
        mi=min(mi,dp[i][last]+cost[i][0]);
    if(mi==maxim)
        cout<<"Nu exista solutie";
    else
        cout<<mi;
}

int main()
{
    f>>n>>m;
    init();
    citire();
    dp[0][1]=0;
    rezolvare();
    for(int i=1;i<20;i++)
    {
        for(int j=1;j<(1<<n);j++)
            g<<setw(10)<<dp[i][j];
        g<<'\n';
    }
    rez();
    return 0;
}