#include <fstream>
#define MAX 18
#define INF 1000000000
using namespace std;
ifstream cin ("hamilton.in");
ofstream cout ("hamilton.out");
int dp[(1 << MAX) + 10][MAX + 10], cost[MAX + 10][MAX + 10];
int main()
{
    int n, m;
    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, c;
        cin >> x >> y >> c;
        cost[x][y] = c;
    }
    for (int conf = 0; conf < (1 << n); conf++)
        for (int i = 0; i < n; i++)
            dp[conf][i] = INF;
    dp[1][0] = 0;
    for (int conf = 1; conf < (1 << n); conf++)
        for (int last = 0; last < n; last++)
            if ((conf >> last) & 1)
                for (int added = 0; added < n; added++)
                    if (!((conf >> added) & 1))
                        dp[conf | (1 << added)][added] = min(dp[conf | (1 << added)][added], dp[conf][last] + cost[last][added]);
    int ans = INF;
    for (int i = 0; i < n; i++)
        ans = min(ans, dp[(1 << n) - 1][i] + cost[i][0]);
    if (ans == INF)
        cout << "Nu exista solutie";
    else
        cout << ans;
    return 0;
}