///Solutia obtine 40p
#include <bits/stdc++.h>
#define INF 0x7F7F7F7F
using namespace std;

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

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);

    memset(C, INF, sizeof C);

    int x, y, c;
	for (int i=0; i<M; ++i) {
		scanf("%d %d %d", &x, &y, &c);
		C[x][y] = c;
	}

    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;
}