#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int dp[1<<18][18], x[18][18];
vector<int> y[1000];

int main() {
    int n, m, a, b, c;
    fin>>n>>m;

    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    x[i][j]=1000000000;

    for(int i=1;i<=m;i++)
    {fin>>a>>b>>c;
     x[a][b]=min(x[a][b], c);
     y[b].push_back(a);
    }

    for(int i=0;i<1<<n;i++)
    for(int j=0;j<n;j++)
    dp[i][j]=1000000000;
    dp[1][0]=0;

    for(int mask=3;mask<(1<<n);mask+=2)
    for(int i=1;i<n;i++)
    if(mask & (1<<i))
    {vector<int> :: iterator j;
     for(j=y[i].begin();j!=y[i].end();j++)
     dp[mask][i]=min(dp[mask][i], dp[mask ^ (1<<i)][*j]+x[*j][i]);
    }
    int mini=1000000000;

    for(int i=1;i<n;i++)
    mini=min(mini, dp[(1<<n)-1][i]+x[i][0]);

    if(mini==1000000000)fout<<"Nu exista solutie";
    else fout<<mini;
    return 0;
}