#include <iostream>
#include <fstream>
#include <vector>
#define oo (1<<30)

using namespace std;

vector <int> v[19];
int cost[19][19];
int d[1<<19][19];

int solve(int a, int cfg, int b)
{
    if (d[cfg][b] != oo)
        return d[cfg][b];

    for (int i=0; i<v[b].size(); i++)
        if (cfg & (1<<v[b][i]))
            if (!(v[b][i] == a && ((cfg ^ (1<<b)) != (1<<a))))
                d[cfg][b] = min(d[cfg][b], solve(a, cfg ^ (1<<b), v[b][i]) + cost[v[b][i]][b]);

    return d[cfg][b];
}

int main()
{
    ifstream f("hamilton.in");
    ofstream g("hamilton.out");

    int a, b, c, n, m, i, j, sol;

    f >> n >> m;

    for (i=0; i<n; i++)
        for(j=0; j<n; j++)
            cost[i][j] = oo;

    for (i=1; i<=m; i++){

        f >> a >> b >> c;
        v[b].push_back(a);
        cost[a][b] = c;
    }

    //for(i=0; i<n; i++)
        for(j=0; j<(1<<(n)); j++)
            for(int k=0; k<n; k++)
                d[j][k] = oo;
    sol = oo;
    d[1][0] = 0;
    for (j=0; j < v[0].size(); j++)
            sol = min(sol, solve(0, (1<<n)-1, v[0][j]) + cost[v[0][j]][0]);

    if(sol != oo)g << sol << "\n";
    else g << "Nu exista solutie\n";

}


/*int d[5][1<<5][8]={0};

struct arc{
    int destinatie, cost;
};

vector<arc>cost[307];

inline int solve(int a, int cfg, int b){

    if(d[a][cfg][b] != oo)
        return d[a][cfg][b];
    int min, ms, i, dest, _cost;
    ms = cfg ^ (1<<b);
    min = oo;
    for(i=0; i<cost[b].size(); i++){
        dest = cost[b][i].destinatie;
        if(cfg & (1<<dest) && dest != a){
            if(d[a][ms][dest] != oo)
                _cost = d[a][ms][dest];
            else
                _cost = solve(a, ms, dest);
            if(_cost != oo)
                _cost += cost[b][i].cost;
            if(_cost < min)
                min = _cost;
        }
    }
    d[a][cfg][b] = min;
    return min;
}

int main(){
    int i, j, n, a, b, c, m;
    ifstream f("hamilton.in");
    ofstream g("hamilton.out");
    f >> n >> m;
    arc _a;
    for(i=1; i<=m; i++){
        f >> a >> b >> c;
        _a.destinatie = a;
        _a.cost = c;
        cost[b].push_back(_a);
    }
    for(i=0; i<n; i++)
        for(j=0; j<=(1<<(n-1)); j++)
            for(int k=0; k<n; k++)
                d[i][j][k] = oo;
    for(i=0; i<n; i++){
        d[i][1<<i][i] = 0;
    }
    int sol = oo;
    for(i=0; i<n; i++){
        for (j = 0; j < cost[i].size(); ++j)
            if(solve(i, (1<<n)-1, cost[i][j].destinatie) + cost[i][j].cost < sol)
                sol = solve(i, (1<<n)-1, cost[i][j].destinatie) + cost[i][j].cost;
    }
    g << sol << "\n";
}


int d[5][1<<5][8]={0};

inline int solve(int a, int b, int cfg){

    if(d[a][cfg][b] < oo)
        return d[a][cfg][b];

    //cout << cfg << "\n";
    int ms, min, cost;
    min = oo;
    ms = cfg ^ (1<<b);
    for(int i=0; (1<<i)<=ms; i++)
        if(ms & (1<<i) && i!=a && d[i][(1<<i) + (1<<b)][b] !=oo){
            if(d[a][ms][i] < oo)
                cost = d[a][ms][i];
            else
                cost = solve(a, i, ms);
            cost += d[i][(1<<i) + (1<<b)][b];
            if(cost < min && cost>-1)
                min = cost;
        }
    cout << min << " " << oo <<"\n";
    d[a][cfg][b] = min;
    return min;
}

int main()
{
    ifstream f("hamilton.in");
    ofstream g("hamilton.out");
    int a, b, c, i, j, n, m, k;
    f >> n >> m;

    for(i=0; i<n; i++){
        for(j=0; j<(1<<n); j++)
            for(k=0; k<n; k++)
                d[i][j][k] = oo;
    }

    for(i=1; i<=m; i++){
        f >> a >> b >> c;
        //a--;
        //b--;
        d[a][(1<<a) + (1<<b)][b] = c;
    }
    for(i=0; i<n; i++)
        d[i][1<<i][i] = 0;
    g << solve(0, n-1, 0) << "\n";

}*/