#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#define NMAX 20

using namespace std;

int m, n;

struct punct
{
    int nod;
    int pret;
    punct(int n=0, int p=0)
    {
        nod = n;
        pret = p;
    }
};

vector<punct> GR[NMAX];
int minim, minGen=1000005;
int viz[NMAX];
void dfs(int elem, int c, int first)
{
    viz[elem] = 1;
    vector<punct>:: iterator it;
    for (it = GR[elem].begin(); it!=GR[elem].end(); it++)
    {
        if (c == n && it->nod == first)
            {
                minim+=it->pret;
                if (minim < minGen)
                    minGen = minim;
                minim-=it->pret;
            }
        if (!viz[it->nod])
        {
            minim+=it->pret;
            dfs(it->nod, c+1, first);
            minim-=it->pret;
        }
    }

    viz[elem] = 0;

}
void solve()
{
    dfs(1, 1, 1);
    cout<<minGen;
}
void read()
{
    scanf("%d %d\n", &n, &m);
    int x, y, z;
    for (int i=1; i<=m; i++)
    {
        scanf("%d %d %d\n", &x, &y, &z);
        GR[x+1].push_back(punct(y+1, z));
    }
}

int main()
{
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);
    read();
    solve();
    return 0;
}