#include<fstream>
#include<cstring>
#include<vector>
#define inf 0x7f7f7f7f
using namespace std;
vector<pair<int, int> > L[18];
int n, m, x, y, z, i, stare, nod, vecin, cost, D[1<<18][18], M[18], urmstare, sol;
ifstream in("hamilton.in");
ofstream out("hamilton.out");
int main()
{
memset(D, 127, sizeof(D));
memset(M, 127, sizeof(M));
in>>n>>m;
for(i=1; i<=m; i++)
{
in>>x>>y>>z;
L[x].push_back(make_pair(y,z));
if(y==0)
{
M[x]=z;
}
}
D[1][0]=0;
for(stare=1; stare<(1<<n); stare++)
{
for(nod=0; nod<n; nod++)
{
if(D[stare][nod]!=inf)
{
for(i=0; i<L[nod].size(); i++)
{
vecin=L[nod][i].first;
cost=L[nod][i].second;
if((stare&(1<<vecin))==0)
{
urmstare=stare+(1<<vecin);
D[urmstare][vecin]=min(D[urmstare][vecin], D[stare][nod]+cost);
}
}
}
}
}
sol=inf;
for(i=1; i<n; i++)
{
if(M[i]!=inf && D[(1<<n)-1][i]!=inf)
sol=min(sol, D[(1<<n)-1][i]+M[i]);
}
sol!=inf?out<<sol:out<<"Nu exista solutie";
return 0;
}