#include <bits/stdc++.h>

using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int nmax = 20;
const int oo = 1e9;
int n, m, dp[19][(1 << nmax) + 5], C[nmax][nmax], ans = oo;
void read()
{
    fin >> n >> m;
    for(int i = 0; i <= n; ++i)
        for(int j = 0; j <= n; ++j)
            C[i][j] = oo;
    for(int i = 1; i <= m; ++i)
    {
        int x, y, z;
        fin >> x >> y >> z;
        C[x][y] = z;
    }
}
void solve()
{
    int S = (1 << n);
    for(int i = 0; i < n; ++i)
        for(int stare = 0; stare < S; ++stare)
            dp[i][stare] = oo;
    dp[0][1] = 0;
    for(int stare = 1; stare < S; ++stare)
        for(int i = 0; i < n; ++i)
            if(dp[i][stare] < oo)
            {
                for(int j = 0; j < n; ++j)
                    if(C[i][j] < oo && !(stare & (1 << j)))
                        dp[j][stare + (1 << j)] = min(dp[j][stare + (1 << j)], dp[i][stare] + C[i][j]);
            }
    for(int i = 1; i < n; ++i)
        if(C[i][0] < oo)
            ans = min(ans, C[i][0] + dp[i][S - 1]);
    if(ans == oo)
        fout << "Nu exista solutie\n";
    else
        fout << ans << "\n";
}
int main()
{
    read();
    solve();
    return 0;
}