#include <iostream>
#include <fstream>
#include <vector>
#define INF1 0x3f3f3f3f

using namespace std;

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

class Graf
{
    int numar_noduri, numar_muchii;
    vector <vector <int>> lista_adiacenta;

public:

    void hamilton_initializare();
    int hamilton(vector <vector <pair <int, int>>>);
};

int Graf :: hamilton(vector <vector <pair <int, int>>> lista)
{
    int x = 1 << numar_noduri, cost_final = INF1;
    int costuri[x][numar_noduri];

    for(int i = 0; i < x; i++)
        for(int j = 0; j < numar_noduri; j++)
            costuri[i][j] = INF1;

    costuri[1][0] = 0;

    for(int i = 0; i < x; i++)
        for(int j = 0; j  < numar_noduri; j++)
            if((1 << j) & i)
                for(int k = 0; k  < lista[j].size(); k++)
                    if((1 << lista[j][k].first) & i)
                        costuri[i][j] = min(costuri[i][j], costuri[i ^ (1 << j)][lista[j][k].first] + lista[j][k].second);

    for(int i = 0; i < lista[0].size(); i++)
        cost_final = min(cost_final, costuri[x - 1][lista[0][i].first] + lista[0][i].second);

    return cost_final;
}

void Graf :: hamilton_initializare()
{
    int capat_stang, capat_drept, cost;
    vector <vector <pair<int, int>>> lista;

    fin >> numar_noduri >> numar_muchii;

    lista.resize(numar_noduri + 2);

    for(int i = 0; i < numar_muchii; i++)
    {
        fin >> capat_stang >> capat_drept >> cost;
        lista[capat_stang].push_back(make_pair(capat_drept, cost));
    }

    cost = hamilton(lista);
    if(cost == INF1)
        fout << "Nu exista solutie";
    else
        fout << cost;

    lista.clear();
}

int main()
{
    Graf x;
    x.hamilton_initializare();

    fin.close();
    fout.close();

    return 0;
}