#include <bits/stdc++.h>
using namespace std;

const int MAX = 18;
const int INF = 1e9;

int dp[1<<MAX][MAX];
int cost[MAX][MAX];

int main()
{
    ifstream cin("hamilton.in");
    ofstream cout("hamilton.out");
    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 mask = 0; mask < (1 << n); ++mask)
        for (int i = 0; i < n; ++i)
            dp[mask][i] = INF;

    for (int i = 0; i < m; ++i)
    {
        int x, y, c;
        cin >> x >> y >> c;
        cost[x][y] = c;
    }

    dp[1][0] = 0;

    for (int mask = 0; mask < (1 << n); ++mask)
    {
        for (int i = 0; i < n; ++i)
        {
            if (mask & (1 << i))
            {
                for (int j = 0; j < n; ++j)
                {
                    if (!(mask & (1 << j)) && cost[i][j] != INF)
                    {
                        int newMask = mask | (1 << j);
                        dp[newMask][j] = min(dp[newMask][j],
                                             dp[mask][i] + cost[i][j]);
                    }
                }
            }
        }
    }

    int fullMask = (1 << n) - 1;
    int ans = INF;

    for (int i = 1; i < n; ++i)
        if (dp[fullMask][i] != INF && cost[i][0] != INF)
            ans = min(ans, dp[fullMask][i] + cost[i][0]);

    if (ans == INF)
        cout << "Nu exista solutie";
    else
        cout << ans;

    return 0;
}