#include<fstream>
#include<vector>
using namespace std;
ifstream cin("hamilton.in");
ofstream cout("hamilton.out");
vector<int> a[21];
int c[262150][21], cost[21][21];
const int inf=100000000;
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cost[i][j]=inf;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        a[y].push_back(x);
        cin>>cost[x][y];
    }
    for(int i=0;i<(1<<n);i++)
        for(int j=0;j<n;j++)
            c[i][j]=inf;
    c[1][0]=0;
    for(int i=0;i<(1<<n);i++)
        for(int j=0;j<n;j++)
            if(i&(1<<j))
                for(int 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]);
    int sol=inf;
    for(int i=0;i<a[0].size();i++)
        sol = min(sol,c[(1<<n)-1][a[0][i]]+cost[a[0][i]][0]);
    if(sol==inf)
        cout<<"Nu exista solutie"<<"\n";
    else
        cout<<sol<<"\n";
}