#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define cin in
#define cout out

using namespace std;

ifstream in("hamilton.in");
ofstream out("hamilton.out");

int n, m, dp[(1 << 19)][20], i, v[20][20], j;

int main()
{
    cin >> n >> m;
    for(i = 1; i <= m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        v[a][b] = c;
    }
    for(i = 0; i <= (1 << n) - 1; ++i)
        for(j = 0; j <= n-1; ++j)
            dp[i][j] = INF;
    dp[1][0] = 0;
    for(int msk = 1; msk <= (1 << n) - 1; ++msk)
        for(i = 0; i < n; ++i) {
            if(!(msk & (1 << i))) continue;
            for(j = 0; j < n; ++j)
                if(v[i][j] && ((msk & (1 << j)) == 0))
                    dp[msk | (1 << j)][j] = min(dp[msk | (1 << j)][j], dp[msk][i]+v[i][j]);
    }
    int mini = INF;
    for(i = 1; i < n; ++i) {
        if(v[i][0])
            mini = min(mini, dp[(1<< n)-1][i] + v[i][0]);
    }
    if(mini == INF) cout << "Nu exista solutie";
    else cout << mini;

    return 0;
}