#include <bits/stdc++.h>

using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
#define pb push_back
#define inf 1 << 30
const int Nmax = 18 + 2;
int n, m, cst[Nmax][Nmax], dp[(1 << Nmax)][Nmax], minim;
vector<int>v[Nmax], vz;
int main()
{
    fin >> n >> m;
    for(int i = 1, a, b, c; i <= m; ++i)
    {
        fin >> a >> b >> c;
        v[a].pb(b);
        cst[a][b] = c;
        if(b == 0)vz.pb(a);
    }

    for(int mask = 1; mask < (1 << n); ++mask)
        for(int nod = 0; nod < n; ++nod)
            dp[mask][nod] = inf;

    dp[1][0] = 0;
    for(int mask = 1; mask < (1 << n); ++mask)
        for(int j = 0; j < n; ++j)
        {
            for(auto fiu : v[j])
                if(dp[mask][j] != inf && !(mask & (1 << fiu)))
                {
                    cout << j << " " << fiu << '\n';
                    dp[mask + (1 << fiu)][fiu] = min(dp[mask + (1 << fiu)][fiu], dp[mask][j] + cst[j][fiu]);
                }
        }

    minim = inf;
    for(auto i : vz)
        minim = min(minim, dp[(1 << n) - 1][i] + cst[i][0]);

    if(minim == inf)fout << "Nu exista solutie";
    else fout << minim;
    return 0;
}