#include<iostream>
#include<fstream>
using namespace std;
#define FIN "hamilton.in"
#define FOUT "hamilton.out"
const int INF = (1 << 30);

ifstream f(FIN);
ofstream g(FOUT);
int visited[20];

int stack[20];
int n,m;
int C[20][20];
int minn = INF;


int init(int k, int masca)
{
    stack[k] = -1;
    return 0;
}

int succesor(int k, int masca)
{
    if(stack[k] < n)
    {
        stack[k]++;
        return 1;
    }
    return 0;

}

int valid(int k, int masca)
{
    if(k != 0)
    {
       if(C[stack[k-1]][stack[k]] == 0)
        return 0;
    }


    for(int i=0;i<k;i++)
    {
        if(stack[i] == stack[k])
            return 0;
    }
    return 1;
}

int solutie(int k, int masca)
{
    if(k == n)
    {
        if(C[stack[k-1]][stack[0]] != 0)
            return 1;
        else return 0;
    }
    else return 0;
}

int tipar(int k, int masca)
{
    int suma = 0;
    for(int i=0;i<n;i++)
    {
        suma += C[stack[i]][stack[i+1]];
    }
    suma += C[stack[n-1]][stack[0]];
    if(minn > suma)
        minn = suma;
    return 0;

}
int back(int k, int masca)
{
    if(solutie(k, masca)) tipar(k, masca);
    else
    {
        init(k, masca);
        while(succesor(k, masca))
        {
            if(valid(k, masca))
                back(k+1, masca);
        }
    }
}

int main()
{

    f >> n;
    f >> m;
    int x,y,z;
    for(int i=1; i<=m; i++)
    {
        f >> x; f >> y; f >> z;
        C[x][y] = z;
    }


    stack[0] = -1;
    back(0,0);
    g << minn;

    return 0;
}