#include<stdio.h>
#include<vector>
#include<set>
using namespace std;

vector<pair <int, int> >T[100];
int viz[19],n,m,sol=5000;


void read()
{
    scanf("%d %d",&n,&m);
    int i,x,y,c;
    for(i=1;i<m;++i)
    {
        scanf("%d %d %d",&x,&y,&c);
        T[x].push_back(make_pair(y,c));
    }
}

void dfs(int k,int cost,int nr)
{
    viz[k]=1;
    for(vector<pair <int, int> >::iterator it=T[k].begin();it!=T[k].end();++it)
    {
        if(!viz[it->first]) dfs(it->first,cost+=it->second,nr+1);
        if(it->first==0 && nr==n) sol=min(sol,cost+it->second);
    }
    viz[k]=0;
}

int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);

    read();
    dfs(0,0,1);
    printf("%d \n",sol);
    return 0;

}