#include <bits/stdc++.h>
#define NMAX 262150
#define INF (int)1e7

using namespace std;

int n, m;
int cost[20][20];
int ans[NMAX][20];

vector<vector<int> > v(20);

int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    cin >> n >> m;

    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cost[i][j] = INF;

    for(int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        v[y].push_back(x);
        cin >> cost[x][y];
    }
    for(int i = 0; i < (1<<n); i++)
        for(int j = 0; j < n; j++)
            ans[i][j] = INF;
    ans[1][0] = 0;
    for(int i = 0; i < (1<<n); i++) {
        for(int j = 0; j < n; j++)
            if(i & (1<<j))
                for(int k = 0; k < (int)v[j].size(); k++)
                    if(i & (1<<v[j][k]))
                        ans[i][j] = min(ans[i][j], ans[i ^ (1<<j)][ v[j][k] ] + cost[v[j][k]][j]);
    }
    int sol = INF;
    for(int i = 0; i < (int)v[0].size(); i++)
        sol = min(sol, ans[(1<<n)-1][v[0][i]] + cost[v[0][i]][0]);

    if(sol == INF) cout << "Nu exista solutie" << '\n';
    else cout << sol << '\n';


    return 0;
}