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

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

void back_ciclu(int k)
{
    for(int x=0; x<N; ++x){
        if (!ap[x]) {
            st[k] = x;
            ap[x] = true;
            if (C[st[k-1]][st[k]] != INF || k==1) {
                if (k == N) {
                    if (C[st[k]][st[1]] != INF) {
                        long long ct = C[st[k]][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] = false;
        }
    }
}
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;

	back_ciclu(1);

	/// afisarea solutiei
	printf("%d\n", SOL);
	return 0;
}