#include <bits/stdc++.h>
#define NMAX 20
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int n, m;
int A[NMAX][NMAX];
int costminim=INT_MAX, cost;
bool v[NMAX];
vector<int> sol;
bool ok=false;
void read();
void bkt(int poz);
int main()
{
    read();
    sol.push_back(0);
    v[0]=1;
    bkt(1);
    if(!ok) fout<<"Nu exista solutie\n";
    else fout<<costminim<<'\n';
    return 0;
}
void bkt(int poz)
{
    if(cost>costminim)  return;
    if(poz==n)
    {
        if(A[sol.back()][0])
        {
            ok=true;
            if(cost+A[sol.back()][0]<costminim)
                costminim=cost+A[sol.back()][0];
        }
        return;
    }
    for(int i=1; i<n; ++i)
    {
        if(v[i])  continue;
        if(A[sol.back()][i])
        {
            cost+=A[sol.back()][i];
            sol.push_back(i);
            v[i]=1;
            bkt(poz+1);
            v[i]=0;
            sol.pop_back();
            cost-=A[sol.back()][i];
        }
    }

}
void read()
{
    fin>>n>>m;
    for(int i=1; i<=m; ++i)
    {
        int x, y, val;
        fin>>x>>y>>val;
        A[x][y]=val;
    }
}