#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
const int INF=0x3f3f3f3f;
int sol=INF, i, j, u, v, k, n, m, d[(1<<18)+1][19], cost[19][19];
vector<int> g[19];
int main()
{
    ifstream in("hamilton.in");
    ofstream out("hamilton.out");
    in>>n>>m;
    memset(cost,INF,sizeof(cost));
    memset(d,INF,sizeof(d));
    for(i=1; i<=m; i++)
    {
        in>>u>>v;in>>cost[u][v];
        g[v].push_back(u);
    }
    d[1][0]=0;
    for(i=0; i<(1<<n); i++)
        for(j=0; j<n; j++)
            if(i&(1<<j))
                for(k=0; k!=g[j].size(); k++)
                    if(i&(1<<g[j][k]))
                        d[i][j]=min(d[i][j], d[i^(1<<j)][g[j][k]]+cost[g[j][k]][j]);
    sol=INF;
    for(i=0; i!=g[0].size(); i++)
        sol=min(sol, d[(1<<n)-1][g[0][i]]+cost[g[0][i]][0]);
    if(sol==INF)out<<"Nu exista solutie\n";
    else out<<sol<<'\n';
    return 0;

}