#include <iostream>
#include <fstream>
#include <cstring>
#include <climits>
#define inf 100000000
#define ll long long
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int cost[20][20],a[1000001][20];
int main()
{
    int i,j,n,m,k,x,y,z;

    f>>n>>m;
    for (i=0; i<=n; i++) for (j=0; j<=n; j++) cost[i][j]=inf;
    for(i=1; i<=m; i++)
    {
        f>>x>>y>>z;
        cost[x][y]=z;
    }
    for (i=0; i<1<<n; i++)
        for (j=0; j<n; j++) a[i][j]=inf;
    a[1][0]=0;
    m=(1<<n)-1;
    for(i=0; i<=m; i++)
        for(j=0; j<n; j++)
            if(i&(1<<j))
            {
                for(k=0; k<n; k++)
                    if (cost[k][j]!=inf)
                        if (a[i^(1<<j)][k]+cost[k][j]<a[i][j]) a[i][j]=a[i^(1<<j)][k]+cost[k][j];
            }
    ll  mn=inf;

    for(i=1; i<n; i++)
        if (cost[i][0]!=inf&&mn>a[m][i]+cost[i][0]) mn=a[m][i]+cost[i][0];
    if(mn==inf)g<<"Nu exista solutie";
    else g<<mn;
    return 0;
}