#include <fstream>
#include <vector>


using namespace std;
#define LCMax 1<<18
#define CMax 20000000
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int C[LCMax][20];
int Cost[20][20];
vector<int> A[20];
int minim(int a,int b)
{
    return a<b?a:b;
}
int main()
{
    int n,m,x,y,z,i,j,k;
    int LMax;
    fin>>n>>m;
    LMax = 1 << n;

    for(i = 0;i < LMax; i++)
        for(j = 0; j < n; j++)
            C[i][j] = CMax;
    for(i = 1; i <= m; i++)
    {
        fin>>x>>y>>z;
        Cost[x][y]=z;
        A[x].push_back(y);

    }
    C[1][0]=0;
    for(i = 0; i< LMax;i++)
        for(j=0;j < n; j++)
            if( (1<<j) & i)
            {
                for(k = 0;k < A[j].size(); k++)
                {
                    int w;
                    w=A[j][k];
                    C[i^(1<<w)][w]=min( C[i^(1<<w)][w], C[i][j] + Cost[j][w]);
                }

            }
    int rez = CMax;
    for(i=0;i<n;i++)
        if(Cost[i][0])rez=min(rez, C[(1<<n)-1][i] + Cost[i][0]);
    if(rez == CMax)fout<<"Nu exista solutie";
        else fout<<rez;
    return 0;
}