#include <bits/stdc++.h>

#define MAX 19
#define FILES freopen("hamilton.in","r",stdin);\
              freopen("hamilton.out","w",stdout);

using namespace std;

int dp[(1<<(MAX-1)) + 5][MAX];

int n, m, a, b, c;
vector<pair<int,int>> v[MAX + 5];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    FILES
    std::cin >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        std::cin >> a >> b >> c;
        a++, b++;
        v[b].push_back({a, c});
    }
    int mask = (1 << n) - 1;
    for(int i = 1; i <= mask; ++i)
    {
        for(int j = 1; j <= n; ++j)
            dp[i][j] = 1e9;
    }
    dp[1][1] = 0;
    for(int i = 1; i <= mask; ++i)
    {
        if(__builtin_popcount(i) == 1)
            continue;
        int cnt = 0;
        for(int j = 1; j <= i; j *= 2)
        {
            cnt++;
            if(i & j)
            {
                int newMask = (i ^ j);
                for(auto k : v[cnt])
                {
                    if((newMask & (1 << (k.first - 1))) == 0)
                        continue;

                    if(dp[newMask][k.first] != 1e9)
                        dp[i][cnt] = min(dp[i][cnt], dp[newMask][k.first] + k.second);
                }
            }
        }
    }
    int best = 1e9;
    for(int i = 1; i <= n; ++i)
    {
        bool ok = 0;
        int cost = 0;
        for(auto j : v[1])
        {
            if(j.first == i)
                ok = 1, cost = j.second;
        }
        if(ok)
            best = min(best, dp[mask][i] + cost);
    }
    if(best == 1e9)
        std::cout << "Nu exista solutie";
    else
        std::cout << best;
}