#include <fstream>
#include <iostream>
#include <list>
#include <cstring>

using namespace std;

int nov,nom,a,sol;
pair<int,int> bc;
list<pair<int,int>> e[60];

void dump(char c[])
{
    int i;
    for(i=0;i<nov;i++)cout<<c[i]+0<<' ';
    cout<<'\n';
    for(i=0;i<nov;i++)cout<<i<<' ';
    cout<<'\n';
}

//total lenght, no vertices covered, vector of vertices covered (set to 2 when repeated), current vertex
int track(int tl,int nvc,char vc[],int cv)
{
    /*cout<<"tl: "<<tl<<" nvc: "<<nvc<<" cv: "<<cv<<'\n';
    dump(vc);
    cout<<"\n\n";*/
    if(nvc==nov&&vc[0]==2)
    {
        if(sol==0)sol=tl;
        else sol=min(sol,tl);
        return 0;
    }
    list<pair<int,int>>::iterator it;
    for(it=e[cv].begin();it!=e[cv].end();it++)
    {
        int nv=it->first,c=it->second;
        if(vc[nv]==1)
        {
            char vcn[nov];
            memcpy(vcn,vc,nov);
            vcn[nv]=2;
            track(tl+c,nvc,vcn,nv);
        }
        else if(vc[nv]==0)
        {
            char vcn[nov];
            memcpy(vcn,vc,nov);
            for(int i=0;i<nov;i++)
                if(vcn[i]==2)vcn[i]=1;
            vcn[nv]=1;
            track(tl+c,nvc+1,vcn,nv);
        }
    }
    return 0;
}

int main()
{
    fstream f("traseu.in",ios::in),g("traseu.out",ios::out);
    f>>nov>>nom;
    for(int i=0;i<nom;i++)
    {
        f>>a>>bc.first>>bc.second;
        a--;bc.first--;
        e[a].push_back(bc);
    }
    //total lenght, no vertices covered, vector of vertices covered (set to 2 when repeated), current vertex
    char v[60];
    memset(v,0,60);
    v[0]=1;
    track(0,1,v,0);
    g<<sol;
}