#include <iostream>
#include <bits/stdc++.h>
#define VMAX 18
#define INF 2000000000
using namespace std;
ifstream fin ("hamilton.in");
ofstream fout ("hamilton.out");


int graf[20][20];
int dp[20][(1ll)<<19];


int main()
{
    ios_base::sync_with_stdio(0);
    int n,m,i,j,k,t,q,nr,minim,maxim,suma;
    fin>>n>>m;
    for(i=0;i<m;i++)
    {
        fin>>j>>k>>t;
        graf[j][k]=t;
        graf[k][t]=t;
    }

    for(i=0;i<n;i++)
    {
        for(int bitmask=0;bitmask< (1ll<<n);bitmask++)
        {
            dp[i][bitmask]=INF;
        }
    }
	dp[0][1] = 0;
	for (int mask = 1; mask < (1ll << n); mask++) {
		for (int i = 0; i < n; i++) {
			if (mask & (1ll << i)) {
				for (int j = 0; j < n; j++) {
					if (i != j && graf[j][i] && (mask & (1ll << j))) {
						dp[i][mask] = min(dp[i][mask], dp[j][mask ^ (1ll << i)] + graf[j][i]);
					}
				}
			}
		}
	}

    minim=INF;
    for(i=1;i<n;i++)
    {
        if(graf[0][i])
            minim=min(minim,dp[i][(1ll<<n)-1]+graf[0][i]);
    }
    if(maxim!=INF)
        fout<<minim<<'\n';
    else
        fout<<"Nu exista solutie\n";



    return 0;
}