#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <ctime>
#include <string>
#include <cstring>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream ff("hamilton.in");
ofstream gg("hamilton.out");
 
int n, m, cc[18][18], dd[1<<18][18];
  
void sol(){
    memset(dd, 0x3f, sizeof(dd));
    for(int i=0;i<n;i++) dd[1<<i][i]=0;
    for(int i=0;i<(1<<n);i++)
    for(int j=0;j<n;j++)
    for(int k=0;k<n;k++)
    if(i&(1<<j) && !(i&(1<<k)) && cc[j][k])
        dd[i|(1<<k)][k]=min(dd[i|(1<<k)][k], dd[i][j]+cc[j][k]);
     
    int s = 0x3f3f3f3f;
    for(int i=0;i<n;i++)
    if(cc[i][0])
        s=min(s, dd[(1<<n)-1][i]+cc[i][0]);
    if(s==0x3f3f3f3f) gg << "Nu exista solutie"; else
    gg << s << "\n";
}
  
int main(){
    int a, b, c;
    ff >> n >> m;
    for(int i=0;i<m;i++){
        ff >> a >> b >> c;
        cc[a][b]=c;
    }
    sol();
}