#include <fstream>
#include <vector>

using namespace std;

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

#define NMAX 19
#define INF 1e9

vector < int > Gt[NMAX];

int N,M;
int dist[NMAX][NMAX],dp[(1<<NMAX)][NMAX];

void init()
{
    int i,j;
    for(i=0; i<=N; i++)
        for(j=0; j<=N; j++)
            dist[i][j]=INF;
    for(i=1; i<=(1<<N); i+=2)
        for(j=0; j<N; j++)
            dp[i][j]=INF;
}

void read()
{
    int i,x,y,c;
    cin>>N>>M;
    init();
    for(i=1; i<=M; i++)
    {
        cin>>x>>y>>c;
        Gt[y].push_back(x);
        dist[x][y]=c;
    }
}

void afis_dp()
{
    int i,j;
    for(i=1; i<(1<<N); i++)
    {
        for(j=0; j<N; j++)
            cout<<dp[i][j]<<" ";
        cout<<endl;
    }
}

void solve()
{
    int i,j,mask;
    dp[1][0]=0;
    for(mask=3; mask<(1<<N); mask+=2)
    {
        for(j=1; j<N; j++)
            if(mask&(1<<j)) /// are bitul j setat pe 1
            {
                for(auto adj:Gt[j])
                {
                    dp[mask][j]=min(dp[mask-(1<<j)][adj]+dist[adj][j],dp[mask][j]);
                }
            }
    }
    int sol = INF;
    for(i=1; i<N; i++)
        sol=min(sol,dp[(1<<N)-1][i]+dist[i][0]);
    if( sol == INF)
        cout<<"Nu exista solutie";
    else cout<<sol;
}


int main()
{
    read();
    solve();
    return 0;
}