#include <bits/stdc++.h>

using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int n, m, dp[20][263000], biti[263000], sol;
int a[20][20];
vector< pair<int, int> > G[20];

int main()
{
    int i, j, z, c, nod;
    fin >> n >> m;
    while(m)
    {
        fin >> i >> j >> c;
        a[i][j] = c;
        G[i].push_back({j, c});
        m--;
    }
    for(i = 1;i <= ((1 << n) - 1);i++)
        biti[i] = __builtin_popcount(i);
    for(auto e : G[0])
    {
        nod = e.first;
        c = e.second;
        dp[nod][1 + (1 << nod)] = c;
    }
    for(i = 2;i < n;i++)
        for(j = 1;j < ((1 << n) - 1);j += 2)
            if(biti[j] == i)
            {
                for(z = 1;z < n;z++)
                    if((j & (1 << z)) > 0 && dp[z][j] > 0)
                    {
                        for(auto e : G[z])
                        {
                            nod = e.first;
                            c = e.second;
                            if(((1 << nod) & j) == 0)
                            {
                                if(dp[nod][j + (1 << nod)] == 0) dp[nod][j + (1 << nod)] = dp[z][j] + c;
                                else dp[nod][j + (1 << nod)] = min(dp[nod][j + (1 << nod)], dp[z][j] + c);
                            }

                        }
                    }
            }
    sol = INT_MAX;
    for(i = 1;i < n;i++)
        if(dp[i][(1 << n) - 1] > 0 && a[i][0] > 0)
            sol = min(sol, dp[i][(1 << n) - 1] + a[i][0]);
    if(sol == INT_MAX)
        fout << "Nu exista solutie";
    else fout << sol;
    fout << "\n";
    fout.close();
    return 0;
}