#include <iostream>
#include <fstream>
#include <cmath>

#define maxn 73
#define infinit pow(2,30)

using namespace std;

int n,m;

int sol[maxn], a[maxn][maxn], viz[maxn];

int cost_actual=0,cost_min=infinit;

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


void back( int k)
{

    if (k==n)
    {
        if ((a[sol[k-1]][sol[0]]!=0) && (cost_actual+ a[sol[k-1]][sol[0]]<cost_min))
            cost_min=cost_actual+ a[sol[k-1]][sol[0]];
    }
    else
        for (int i=0; i<n; i++)
        {
            if ((k!=0) && (a[sol[k-1]][i]!=0) && (!viz[i]) && (cost_actual + a[sol[k-1]][i]<cost_min))
            {
                viz[i]=1;
                sol[k]=i;
                cost_actual=cost_actual+ a[sol[k-1]][i];
                back(k+1);
                cost_actual=cost_actual-a[sol[k-1]][i];
                viz[i]=0;

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

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


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

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