//#include <iostream>
#include <bits/stdc++.h>
using namespace std;
vector < pair<int,int> >v[20];
ifstream in("hamilton.in");
ofstream out("hamilton.out");
int n,m,viz[20],sum,nr,costmin;
void dfs(int nod)
{
    viz[nod]=1;
    nr++;
    for(int j=0;j<v[nod].size();j++)
    {
        int vecin=v[nod][j].first;
        int cost=v[nod][j].second;
        if(!viz[vecin])
        {
            sum+=cost;
            dfs(vecin);
            nr--; sum-=cost;
        }
        if(nr==n && vecin==0)
          costmin=min(costmin,sum+cost);
    }
    viz[nod]=0;
}
int main()
{
    in>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z; in>>x>>y>>z;
        v[x].push_back({y,z});
    }
    costmin=INT_MAX;
    dfs(0);
    if(costmin==INT_MAX)
        out<<"Nu exista solutie";
    else
        out<<costmin;
    return 0;
}