#include <fstream>
#include <vector>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int n,m,x,y,c,vecin;
int val, d[(1<<18)][19], sol=20000000, ok[50];
vector<pair<int, int> > a[50];


 int main(){
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        fin>>x>>y>>c;
        a[x].push_back(make_pair(y, c));
        if(y==0){
            ok[x]=c;
        }

    }



    x=(1<<n)-1;
    for(int i= 1;i<= x; i += 2){
        for(int j=0;j<n;j++){
            d[i][j] =20000000;

        }
    }


    d[1][0] = 0;

    for(int stare = 1;stare <=x; stare += 2)
        for(int i=0;i<n;i++){
            y = (1<<i);
            if((stare & y) != 0){
                for(int j=0;j<a[i].size();j++){
                    vecin=a[i][j].first;
                    val=a[i][j].second;
                    c=(1<<vecin);
                    if((stare&c) == 0){
                        d[stare+c][vecin] = min(d[stare+c][vecin], d[stare][i] + val);
                    }


                }
            }


        }

    for(int i=1;i<n;i++){
        if(ok[i]!= 0){
            sol = min(sol, d[x][i] + ok[i]);
        }
    }





    if(sol == 20000000){
        fout<<"Nu exista solutie";
    }

    else{
        fout<<sol;
    }



    return 0;

}