#include <fstream>
#define inf 400000000
#include <vector>

using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int n, a, b, c, i, j, stare_max, stare, caracteristic, vecin, d[20][3000000], rad[20], m, car_vecin;
vector<pair<int, int> > v[20];

int main(){
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>a>>b>>c;
        v[a].push_back({b, c});
        if(b == 0)
            rad[a] = c; /// trebuie sa stiu din ce noduri ma pot intoarce in radacina, pentru ca eu nu o sa calculez
        /// costul total pana in zero (zero va fi deja marcat in toate starile posibile)
    }
    stare_max = (1<<n)-1;
    for(i=0;i<n;i++)
        for(stare=0;stare<=stare_max;stare++)
            d[i][stare] = inf;
    d[0][1] = 0;    /// 2^0 = 1 (Starea in care l-am inclus doar pe zero)
    for(stare=1;stare<=stare_max;stare++){
        for(i=0;i<n;i++){
            caracteristic = (1<<i);
            if(stare & caracteristic){   /// daca i se regaseste in starea pe care o analizez eu acum
                for(j=0;j<v[i].size();j++){     /// vad in ce noi stari pot ajunge
                    vecin = v[i][j].first;
                    car_vecin = (1<<vecin);
                    if((stare & car_vecin) == 0)/// daca vecinul nu se afla in starea analizata, astfel incat sa il pot adauga
                        d[vecin][stare+car_vecin] = min(d[vecin][stare+car_vecin], d[i][stare] + v[i][j].second);
                }
            }
        }
    }
    int sol = inf;
    for(i=1;i<n;i++)
        if(rad[i])
            sol = min(sol, d[i][stare_max] + rad[i]);
    if(sol == inf)
        fout<<"Nu exista solutie";
    else
        fout<<sol;
    return 0;
}