#define inf 100000000
#include <bits/stdc++.h>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
vector<pair <int,int> > M[100];
int C[100][100];
int main()
{
    int n,i,x,y,c,m,j,vecin,cost,k,total;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        M[x].push_back({y,c});
    }
    x=1<<n;
    for(i=0; i<x;i++)
		for(j=0; j<n;j++) C[i][j] = inf;
    C[1][0]=0;
    for(i=0;i<n;i++)  ///noduri
        for(k=0;k<x;k++) ///configuratii
           // if (k & (1<<i))
                {
                    for(j=0;j<M[i].size();j++) ///vecini
                    //if(k& (1<<M[i][j].first))
                    {
                        vecin=M[i][j].first;
                        cost=M[i][j].second;
                        C[k][vecin]=min(C[k][vecin], C[k ^(1<<i)][i] + cost);
                    }
                }
    total=inf;
    for(i=0;i<M[0].size();i++)
        total=min(total, C[1<<n-1][M[0][i].first]+M[0][i].second);

    fout<<total;
    return 0;
}