#include <bits/stdc++.h>

using namespace std;
ifstream r("hamilton.in");
ofstream w("hamilton.out");
vector<int>g[20];
int n, m, cost[20][20], d[262150][20];
int main()
{
    r>>n>>m;
    memset(cost, 1e9, sizeof(cost));
    memset(d, 1e9, sizeof(d));
    for(int i=1;i<=m;i++)
    {
        int x, y;
        r>>x>>y;
        r>>cost[x][y];
        g[y].push_back(x);
    }
    d[1][0]=0;
    for(int i=1;i<(1<<n);i++)
    {
        for(int j=0;j<n;j++)
        {
            if(i&(1<<j)!=0)
            {
                for(int k=0;k<g[j].size(); k++)
                {
                    if(i&(1<<g[j][k])!=0)
                    {
                        d[i][j] = min(d[i][j], d[i^(1 << j)][g[j][k]]+cost[g[j][k]][j]);
                    }
                }
            }
        }
    }
    int rez = 1e9;
    for(int i=0;i<g[0].size();i++)
    {
        rez = min(rez, d[(1<<n) - 1][g[0][i]] + cost[g[0][i]][0]);
    }
    if(rez == 1e9)
    {
        w<<"Nu exista solutie\n";
    }
    else
    {
        w<<rez<<"\n";
    }
    return 0;
}