#include <fstream>
#include <vector>
using namespace std;
ifstream fi("hamilton.in");
ofstream fo("hamilton.out");
#define INF 100000000
 
int j,i,x,y,n,m,c[1<<19][20],cost[20][20],sol=INF;
vector< int > a[20];
 
int main(){
     
    fi >> n >> m;
     
    for (i=0; i<n; i++) for (j=0; j<n; j++) cost[i][j]=INF;
     
    for (i=1; i<=m; i++){
        fi >> x >> y;
        a[y].push_back(x);
        fi >> cost[x][y];
    }
 
    for (i=0; i<1<<n; i++) for (j=0; j<n; j++) c[i][j]=INF;
    c[1][0]=0;
     
    for (i=0; i<1<<n; i++)
        for (j=0; j<n; j++)
            if (i & (1<<j))
                for (size_t k=0; k<a[j].size(); k++)
                    if (i & (1<<a[j][k]))
                        c[i][j]=min(c[i][j],c[i^(1<<j)][a[j][k]]+cost[a[j][k]][j]);
         
    for (size_t k=0; k<a[0].size(); k++)
        sol=min(sol,c[(1<<n)-1][a[0][k]]+cost[a[0][k]][0]);
     
    if (sol==INF) fo << "Nu exista solutie"; else fo << sol;           
                     
    return 0;
}