#include <fstream>
#include <vector>
#include <iomanip>
#define maxd ((1<<18)+5)
#define maxn 20
#define inf (1<<26)
using namespace std;

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

vector<int> v[maxn];
int C[maxd][maxn];
int cost[maxn][maxn];

int i,j,k,n,m,x,y,c,rasp=inf;


int main()
{
    f>>n>>m;


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

    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>>c;
            v[y].push_back(x);
            v[x].push_back(y);
            cost[x][y]=c;
        }

    C[1][0]=0;

    for (i=0;i<(1<<n);++i)
        for(j=0;j<n;++j)
            if (i & (1<<j))
                for (k=0;k<v[j].size();++k)
                {
                    x = v[j][k];
                    if (i && (1<<x))
                        C[i][j]=min(C[i][j],C[i^(1<<j)][x] + cost[x][j]);
                }

    for (i=0;i<v[0].size();++i)
            rasp=min(rasp,C[(1<<n)-1][v[0][i]] + cost[v[0][i]][0]);

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


    return 0;
}