#include <bits/stdc++.h>
#define bug(a) std::cerr << "(" << #a << ": " << a << ")\n";
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
const int inf=2e7;
int main()
{
    ifstream cin("hamilton.in");
    ofstream cout("hamilton.out");
    int n,m;
    cin>>n>>m;
    if(n==1)
    {
        cout<<0;
        return 0;
    }
    uniform_int_distribution<int> ui(0,n-1);
    uniform_real_distribution<double> uf(0.0f,1.0f);
    vector<vector<int>>cost(n,vector<int>(n,inf));
    for(int i=0;i<m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        cost[x][y]=z;
    }
    vector<int>v(n);
    iota(all(v),0);
    int sol,acm,x,y;
    auto calculate=[&](const vector<int>&x)->int
    {
        int rez=0;
        for(int i=1;i<n;i++)
        {
            rez+=cost[x[i-1]][x[i]];
        }
        rez+=cost[x[n-1]][x[0]];
        return rez;
    };
    auto modify=[&]()
    {
        x=ui(mt);
        y=x;
        while(y==x)
        {
            y=ui(mt);
        }
    };
    sol=acm=calculate(v);
    double init=clock();
    int step=0;
    do
    {
        acm=calculate(v);
        sol=std::min(sol , acm);
    }while(next_permutation(all(v)));
    if(sol>=inf)
    {
        cout<<"Nu exista solutie";
        return 0;
    }
    cout<<sol;

}