#include <iostream>
#include <fstream>


#define maxn 80
#define infinity 1000000000

using namespace std;

int n,m;

int sol[maxn], c[maxn][maxn], mark[maxn];

int cost=0,minim=infinity;

ifstream in("hamilton.in");
ofstream out("hamilton.out");


void back(int k)
{

    if (k==n)
    {
        if ((c[sol[k-1]][sol[0]]!=0) && (cost + c[sol[k-1]][sol[0]]<minim))
            minim=cost+c[sol[k-1]][sol[0]];
    }
    else
        for (int i=0; i<n; i++)
        {
            if ((k!=0) && (c[sol[k-1]][i]!=0) && (!mark[i]) && (cost + c[sol[k-1]][i]<minim))
            {
                mark[i]=1;
                sol[k]=i;
                cost=cost+c[sol[k-1]][i];
                back(k+1);
                cost=cost-c[sol[k-1]][i];
                mark[i]=0;

            }
            else
                if (k==0)
                {
                    sol[k]=i;
                    mark[i]=1;
                    back(k+1);
                    mark[i]=0;
                }
        }
}

    int main()
    {
        int x,y,cc;
        in>>n>>m;


        for (int i=0; i<m; i++)
        {
            in>>x>>y>>cc;
            c[x][y]=cc;
        }

        back(0);
        out<<minim;
        return 0;
    }