#include <bits/stdc++.h>

using namespace std;

const int INF = (1 << 30), NMAX(20);
using VI  = vector<int>;
using VVI = vector<VI>;
using VB  = vector<bool>;

void BUNA(const string& task = "")
{
    if (!task.empty())
        freopen((task + ".in").c_str(), "r", stdin),
                freopen((task + ".out").c_str(), "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
void PA()
{
    exit(0);
}

int cost[NMAX][NMAX], dp[(1 << NMAX)][NMAX];
vector<int> G[NMAX];

int main()
{
    BUNA("hamilton");
    int n, m;
    cin >> n >> m;

    for(int i = 1; i <= m; ++i)
    {
        int x, y, c;
        cin >> x >> y >> c;

        cost[x][y] = c;
        G[x].push_back(y);
    }

    for(int msk = 0; msk < (1 << n); ++msk)
        for(int i = 0; i < n; ++i)
            dp[msk][i] = INF;

    dp[1][0] = 0;
    for(int msk = 1; msk < (1 << n); ++msk)
        for(int i = 0; i < n; ++i)
            if((1 << i) & msk)
                for(auto j: G[i])
                    if((1 << j) & msk)
                        dp[msk][j] = min(dp[msk][j], dp[msk - (1 << j)][i] + cost[i][j]);
    int rez = INF;
    for(int i = 1; i < n; ++i)
        if(dp[(1 << n) - 1][i] < INF && cost[i][0] > 0)
            rez = min(rez, dp[(1 << n) - 1][i] + cost[i][0]);
    if(rez == INF)
        cout << "Nu exista solutie\n";
    else cout << rez << '\n';
    PA();
}