#include <fstream>
using namespace std;
int n,m,start[20],t[3][310],viz[20],smin=1000001,stiva[20],d[20],st[20];
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
void citire()
{
    int k=0,a,b,c,i;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        k++;
        t[0][k]=b;
        t[1][k]=start[a];
        t[2][k]=c;
        start[a]=k;
        if (b==0)d[a]=c;//d[i] este diferit de zero daca am arc de la i la 1, iar d[i] este atunci costul
    }
}
void rezolv()
{
    int s=0,vf=0,k=0,i;
    k++;
    stiva[k]=vf;
    st[k]=0;
    viz[vf]=1;
   while(k>0)
    {
        if (st[k]==0)i=start[stiva[k]];//daca st[k]==0 inseamna ca tocmai am urcat la nivelul k
        else i=t[1][st[k]];//daca nu inseamna ca a avut loc un k-- si mai cautam si alti vecini nevizitati pentru stiva[k]
        while(i!=0 && viz[t[0][i]]==1) i=t[1][i];
        if(i!=0)
        {
            st[k]=i;//pastrez pozitia din t de unde l-am luat pe noul vecin al lui stiva[k]
            k++;//urc
            stiva[k]=t[0][i];//noul vecin
            viz[t[0][i]]=1;//vizitez
            st[k]=0;//tocmai am urcat si initializez cautarea de la inceput
            s=s+t[2][i];//suma creste cu costul corespunzator
            if (k==n)
            {
                if (d[stiva[n]]>0 && s+d[stiva[n]]<smin)
                {
                    smin=s+d[stiva[n]];
                }
            }
        }
        else
        {
            viz[stiva[k]]=0;//renunt la stiva[k]
            k--;//cobor
            s=s-t[2][st[k]];//scot din suma
        }
    }
    fout<<smin;
    fout.close();
}
int main()
{
    citire();
    rezolv();
    return 0;
}