#include <cstdio>
#define INF 20000000 /// "+infinit" pe int
using namespace std;

int st[21];
bool ap[21];
int C[21][21];
int N, M, SOL;

void back_ciclu(int k)
{
    for(int x=0; x<N; ++x){
        if (!ap[x]) {
            st[k] = x;
            ap[x] = 1;
            if (C[st[k-1]][st[k]] != INF) {
                if (k == N) {
                    if (C[st[k]][st[1]] != INF) {
                        int ct = 0;
                        st[N+1] = st[1];
                        for(int i=1; i<=N; ++i)
                            ct += C[st[i]][st[i+1]];
                        if (ct < SOL) SOL = ct;
                    }
                }
                else back_ciclu(k+1);
            }
            ap[x] = 0;
        }
    }
}
int main()
{
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out","w", stdout);

	/// citirea datelor
	scanf("%d %d", &N, &M);
	for(int i=0; i<N; ++i)
        for(int j=0; j<N; ++j)
            C[i][j] = INF; ///matricea costurilor
    int x, y, c;
	for (int i=0; i<M; ++i) {
		scanf("%d %d %d", &x, &y, &c);
		C[x][y] = c;
	}

	/// calcularea solutiei
	SOL =  INF;
    st[1] = ap[1] = 1;

	back_ciclu(2);

	/// afisarea solutiei
	if (SOL >= INF) printf("Nu exista solutie\n");
               else printf("%d\n", SOL);
	return 0;
}