#include <bits/stdc++.h>

using namespace std;

int a[20][20];
int x[20];

bool bun(int j) {
    for(int i = 1; i < j; i ++)
        if(x[i] == x[j])
            return false;
    return true;
}

int main()
{
    FILE *f = fopen("hamilton.in", "r");
    FILE *g = fopen("hamilton.out", "w");

    int n, m, X, Y;
    fscanf(f, "%d %d", &n, &m);
    for(int i = 1; i <= m; i ++) {
        fscanf(f, "%d %d", &X, &Y);
        fscanf(f, "%d", &a[X + 1][Y + 1]);
    }

    for(int i = 0; i <= n; i ++)
        a[0][i] = 1;
    int i = 1, mn = 18000000;
    while(i != 0) {
        while(i != 0 && i <= n) {
            x[i] ++;
            if(x[i] > n) x[i] = 0, i --;
            else if(bun(i) && a[x[i - 1]][x[i]]) i ++;
        }
        if(i > n) {
            if(a[x[n]][x[1]]) {
                int s = 0;
                for(int j = 2; j <= n; j ++) {
                    s += a[x[j - 1]][x[j]];
                }
                s += a[x[n]][x[1]];
                mn = min(s, mn);
            }
            i = n;
        }
    }
    fprintf(g, "%d\n", mn);
    return 0;
}