#include <fstream>
#include <vector>
#include <queue>
#define INF 1000000000
#define DIM 20
using namespace std;
ifstream fi("hamilton.in");
ofstream fo("hamilton.out");
int n,m;
vector<pair<int,int> > V[DIM];
int D[(1<<DIM)][DIM];
int C[DIM][DIM];
int rez=INF;
int main()
{
    fi>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            C[i][j]=INF;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        fi>>a>>b>>c;
        V[a].push_back(make_pair(b,c));
        C[a][b]=c;
    }
    for(int i=0;i<(1<<n);i++)
        for(int j=0;j<n;j++)
            D[i][j]=INF;
    D[1][0]=0;
    for(int i=0;i<(1<<n);i++)
        for(int j=0;j<n;j++)
                for(auto it:V[j])
                    if(!(i&(1<<it.first)))
                        D[i+(1<<it.first)][it.first]=min(D[i+(1<<it.first)][it.first],D[i][j]+it.second);
    for(int i=0;i<n;i++)
        rez=min(rez,D[(1<<n)-1][i]+C[i][0]);
    if(rez==INF)
        fo<<"Nu exista solutie";
    else
        fo<<rez;
    fi.close();
    fo.close();
    return 0;
}