#include <bits/stdc++.h>
#define int long long
#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=100'000'000;
main()
{
    ifstream cin("hamilton.in");
    ofstream cout("hamilton.out");
    int n,m;
    cin>>n>>m;
    if(n==1)
    {
        cout<<0;
        return 0;
    }
    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);
    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;
    };
    int sol=calculate(v);
    do
    {
        int acm=calculate(v);
        sol=std::min(sol , acm);
    }while(next_permutation(all(v)));
    if(sol>=inf)
    {
        cout<<"Nu exista solutie";
        return 0;
    }
    cout<<sol;

}