#include <bits/stdc++.h>
#define N 18
#define INF 0x3F3F3F3F
#define min(a, b) a<b?a:b
using namespace std;

int dist[N][N], dp[1<<N][N];
int main () {
    ifstream fin ("hamilton.in");
    ofstream fout ("hamilton.out");
    ios::sync_with_stdio(false);

    cout << (sizeof dp + sizeof dist)*1.0/1024.0/1024.0;
    int n, m;
    fin >> n >> m;

    memset(dist, INF, sizeof dist);
    memset(dp, INF, sizeof dp);
    dp[1][0]=0;

    int i, j;
    for (; m; m--)
        fin >> i >> j >> dist[i][j];

    int mask;
    for (mask=1; mask< 1<<n; mask++)
        for (i=0; i<n; i++)
            if (mask & (1<<i))
                for (j=0; j<n; j++)
                    if (mask & (1<<j))
                        dp[mask][i]=min(dp[mask][i], dp[mask ^ (1<<i)][j] + dist[j][i]);

    int ans=INF;
    for (i=0; i<n; i++)
        ans=min(ans, dp[(1<<n)-1][i] + dist[i][0]);

    if (ans==INF)
        fout << "Nu exista solutie";
    else
        fout << ans;
    return 0;
}