#include <fstream>
#include <vector>
#include <utility>

using namespace std;

const int NMAX = 18;
const int INF = 1E9;

int N, M;
vector <pair <int, int> > graph[NMAX + 1];

int dp[NMAX][1 << NMAX];

int main()
{
    ifstream cin("hamilton.in");
    ofstream cout("hamilton.out");

    cin >> N >> M;

    for (int i = 0; i < M; ++ i) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[b].push_back(make_pair(a, c));
    }

    dp[0][1] = 0;
    for (int mask = 3; mask < (1 << N); mask += 2)
        for (int node = 0; node < N; ++ node)
            if (mask & (1 << node)) {
                dp[node][mask] = INF;
                for (int i = 0; i < graph[node].size(); ++ i) {
                    if (mask & (1 << graph[node][i].first)) {
                        int aux = dp[graph[node][i].first][mask ^ (1 << node)] + graph[node][i].second;
                        if (aux < dp[node][mask])
                            dp[node][mask] = aux;
                    }
                }
            }

    int ans = INF;
    for (int i = 0; i < graph[0].size(); ++ i) {
        int someone = graph[0][i].first;
        int cost = graph[0][i].second;
        int aux = dp[someone][(1 << N) - 1] + cost;
        if (aux < ans)
            ans = aux;
    }

    if (ans == INF)
        cout << "Nu exista solutie\n";
    else
        cout << ans << '\n';
    return 0;
}