#include <iostream>
#include <fstream>
#include <vector>
using namespace std;


ifstream fin("hamilton.in");
ofstream fout("hamilton.out");


int n,m;
int c[20][20];
int dp[262150][20];


vector <int> v[20];


void read()
{
    fin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)c[i][j]=1e9;
    int x,y;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;
        v[y].push_back(x);
        fin>>c[x][y];
    }
}


void ham()
{
    for(int i=0;i< 1<<n;i++)
        for(int j=0;j<n;j++)dp[i][j]=1e9;
    dp[1][0]=0;
    for(int i=0;i< 1<<n;i++)
        for(int j=0;j<n;j++)
            if(i & (1<<j))
                for(int k=0;k<v[j].size();k++)
                    if(i & (1<<v[j][k]))dp[i][j]=min(dp[i][j],dp[i^(1<<j)][v[j][k]]+c[v[j][k]][j]);
    int ans=1e9;
    for(int i=0;i<v[0].size();i++) ans=min(ans,dp[(1<<n)-1][v[0][i]]+c[v[0][i]][0]);
    if(ans==1e9) fout<<"Nu exista solutie";
    else fout<<ans;
}


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