#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>

using namespace std;

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

vector <int> v[2000];
int n, m, a,c, b,st[100], maxi=999999999,hamilton=0,freq[1000], nr;
int cost[100][100];
void ham(int nod, int nr)
{
    if(hamilton==1)
       {
           int s=0;
           for(int i=0;i<n;i++)
               {

               s+=cost[st[i]][st[i+1]];

            //cout<<i<<" "<<i+1<<" "<<cost[i][i+1]<<endl;
               }
                s+=cost[n][0];

           if(s<maxi)
            maxi=s;
           hamilton=0;
       }
    else
    {
        st[nr]=nod;
        freq[nod]=1;
        for(int i=0;i<v[nod].size();i++)
        {
            if(freq[v[nod][i]]==0)
                ham(v[nod][i], nr+1);
            if(n-1==nr && v[nod].end()!=find(v[nod].begin(),v[nod].end(),0))
                {hamilton=1;
                ham(nod,nr);
                }
        }

    freq[nod]=0;
    }
}




int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        cost[a][b]=c;
        v[a].push_back(b);
       // v[b].push_back(a);

    }

    ham(0,nr);



    //cout<<hamilton;
    fout<<maxi;
//    for(int i=0;i<n;i++)
//        fout<<st[i]<<" ";



    return 0;
}