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

#define NMax 20
#define XMax 1048576
#define inf 2100000000

ifstream f("hamilton.in");
ofstream g("hamilton.out");

int n,m;
int Cost[NMax][NMax];
int C[XMax][NMax];
vector<int> v[NMax];

int main()
{
    int i,j,k,a,b;

    f>>n>>m;

    int N=(1<<n);

    for(i=0;i<n;i++) for(j=0;j<n;j++) Cost[i][j]=inf;
    for(i=0;i<N;i++) for(j=0;j<n;j++) C[i][j]=inf;

    for(i=1;i<=m;i++)
    {
        f>>a>>b;
        v[b].push_back(a);
        f>>Cost[a][b];
    }

    C[1][0]=0;

    for(i=1;i<N;i++) for(j=0;j<n;j++) for(k=0;k<(int)v[j].size();k++)
        C[i][j] = min(C[i][j], C[i ^ (1<<j)][ v[j][k] ] + Cost[ v[j][k] ][j]);

    int sol=inf;
    for(k=0;k<(int)v[0].size();k++)
        sol=min(sol,C[N-1][ v[0][k] ] + Cost[ v[0][k] ][0]);

    if(sol==inf) g<<"Nu exista solutie\n";
    else g<<sol<<"\n";

    f.close();
    g.close();
    return 0;
}