#include <iostream>
#include <fstream>
#include <vector>

const int MAXN = 18 + 1;

using namespace std;

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

vector<pair<int,int> >graf[MAXN];
/// dp[i][numar] inseamna costul minim de a ajunge din nodul 0 in nodul folosind nodurile marcate in numar cu bitii 1
/// dp[i][numar] = dp[j][ceva] + (1<<i)
int dp[MAXN][(1<<MAXN) + 5];
int n,m;

void Noduri(int val){
    cout<<"Noduri : ";
    for(int i = 0; i <= (1<<n) && i <= val; i++){
        if((val & (1<<i)) > 0)
            cout<<i<<" ";
    }
    cout<<"; ";
}
void afisare(){
    /// 0,2,4 -> 2^0 + 2^2 + 2^4 = 1 + 4 + 16 = 21
    cout<<dp[1][31]<<" "<<(1<<n) - 1<<endl;
    for(int nod = 1; nod <= n - 1; nod++){
        cout<<"Nodul "<<nod<<": ";
        for(int i = 1; i <= 31; i++)
            if(dp[nod][i] != 2e9)
                Noduri(i);
        cout<<endl;
    }
}

int main()
{
    in>>n>>m;
    for(int i = 1; i <= m; i++){
        int x,y,cost;
        in>>x>>y>>cost;
        graf[x].push_back({y,cost});
    }
    for(int i = 1; i < n; i++){
        for(int j = 1; j <= (1<<n); j++)
            dp[i][j] = 2e9;
    }
    for(int masca = 0; masca <= (1<<n); masca++){
        for(int nod = 0; nod <= n - 1; nod++){
            if(dp[nod][masca] == 2e9)
                continue;
            for(int i = 0; i < graf[nod].size(); i++){
                int vecin = graf[nod][i].first;
                int cost = graf[nod][i].second;
                if((masca & (1<<vecin)) > 0 || (dp[nod][masca] == 0 && masca != (1<<nod)))
                    continue;
                dp[vecin][masca + (1<<vecin)] = min(dp[vecin][masca + (1<<vecin)],dp[nod][masca] + cost);

            }
        }
    }
    int raspuns = 2e9;
    for(int nod = 1; nod <= n - 1; nod++){
        for(int i = 0; i < graf[nod].size(); i++){
            int vecin = graf[nod][i].first;
            int cost = graf[nod][i].second;
            int maxim = (1<<n) - 1;/// 2^0 + 2^1 + ... 2 ^ (n - 1)  = 2^0 + 2^0 + 2^1 + ... 2 ^ (n - 1) - 1 = 2 ^ n - 1
            if(vecin == 0 && dp[nod][maxim])
                raspuns = min(raspuns,dp[nod][maxim] + cost);
        }

    }
    if(raspuns == 2e9)
        out<<"Nu exista solutie";
    else
        out<<raspuns;
    return 0;
}