#include <iostream>
#include <stdio.h>
#include <vector>


using namespace std;
const int NMAX = 18, INF = 1e9;

struct pack {
    int nd, cst;
};

int dp[1 << NMAX][NMAX];
int d[NMAX];
vector<pack> adj[NMAX];

int main()
{
    int n, m, i, j, nd, nd1, nd2, prv, mask, cst, minn;
    FILE *fin = fopen("hamilton.in", "r");

    fscanf(fin, "%d%d", &n, &m);

    for (nd = 0; nd < n; nd++)
        d[nd] = INF;
    for (i = 0; i < m; i++) {
        fscanf(fin, "%d%d%d", &nd1, &nd2, &cst);

        if (nd2 == 0)
            d[nd1] = cst;
        else
            adj[nd2].push_back({nd1, cst});
    }
    fclose(fin);


    for (mask = 2; mask < (1 << n); mask ++)
        for (nd = 0; nd < n; nd++)
            dp[mask][nd] = INF;

    dp[1][0] = 0;
    for (mask = 3; mask < (1 << n); mask += 2)
        for (nd = 1; nd < n; nd++) {

            if ((mask & (1 << nd)) == 0)
                continue;

            int len = adj[nd].size();

            for (i = 0; i < len; i++) {
                prv = adj[nd][i].nd, cst = adj[nd][i].cst;
                if (mask & (1 << prv))
                    dp[mask][nd] = min(dp[mask][nd], dp[mask ^ (1 << nd)][prv] + cst);
            }
        }

    minn = INF;
    for (nd = 1; nd < n; nd++)
        minn = min(minn, dp[(1 << n) - 1][nd] + d[nd]);

    FILE *fout = fopen("hamilton.out", "w");
    if (minn >= INF)
        fprintf(fout, "Nu exista solutie");
    else
        fprintf(fout, "%d", minn);
    fclose(fout);


    return 0;
}