#include <bits/stdc++.h>

using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
const int N = 18;
const int P = 1<<17;
int n,m,M,x,y,c[N][N],s,i,j,k,d[P][17],cost;
vector<int> S,D;
int main()
{
    f>>n>>m;
    for(; m; m--)
    {
        f>>x>>y;
        f>>c[x][y];
    }
    s=n-1;
    n--;
    for(i=0; i<s; i++)
        if(c[s][i])
            d[1<<i][i]=c[s][i];
    k=(1<<n)-1;
    for(m=1; m<k; m++)
    {
        S.resize(0);
        D.resize(0);
        for(i=0,j=1; i<n; i++,j<<=1)
        {
            if(m&j)
            {
                if(d[m][i])
                    S.push_back(i);
            }
            else
                D.push_back(i);
        }
        for(auto is:S)
            for(auto id:D)
                if(c[is][id])
                {
                    M=m|(1<<id);
                    if(!d[M][id])
                        d[M][id]=d[m][is]+c[is][id];
                    else if(d[M][id]>d[m][is]+c[is][id])
                        d[M][id]=d[m][is]+c[is][id];
                }
    }
    cost=20000000;
    for(i=0; i<n; i++)
        if(d[k][i]&&c[i][s])
            cost=min(cost,d[k][i]+c[i][s]);
    if(cost==20000000)
        g<<"Nu exista solutie";
    else
        g<<cost;
    return 0;
}