#include<fstream>
#define NMAX 19
#define SMAX 524288
#define INF 2000000000
using namespace std;
int n, m, x, y, z;
int dist[NMAX + 5][NMAX + 5];
int stare, path, b, n_stage;
int d[SMAX + 5][NMAX + 5];
int sol;
ifstream cin("hamilton.in");
ofstream cout("hamilton.out");
void init()
{
    for(stare = 0; stare < (1 << n); stare++)
    {
        for(int i = 0; i < n; i++)
        {
            d[stare][i] = INF;
        }
    }
    d[1][0] = 0;
}
void cicle_finish()
{
    sol = INF;
    for(int i = 0; i < n; i++)
    {
        if(dist[i][0] != INF)
        {
            sol = min(d[(1 << n) - 1][i] + dist[i][0], sol);
        }
    }
}
void hamilton()
{
    init();
    for(stare = 1; stare < (1 << n); stare++)
    {
        for(int i = 0; i < n; i++)
        {
            if(d[stare][i] != INF)
            {
                for(b = 0; b < n; b++)
                {
                    if((stare & (1 << b)) == 0 && dist[i][b] != INF)
                    {
                        n_stage = stare + (1 << b);
                        if(d[n_stage][b] > d[stare][i] + dist[i][b])
                        {
                            d[n_stage][b] = d[stare][i] + dist[i][b];
                        }
                    }
                }
            }
        }
    }
    cicle_finish();
}
main_init()
{
    for(int i = 0; i < NMAX; i++)
    {
        for(int j = 0; j < NMAX; j++)
        {
            dist[i][j] = INF;
        }
    }
}
void afisare()
{
    if(sol == INF)
    {
        cout << "Nu exista solutie";
    }else
    {
        cout << sol;
    }
}
int main()
{
    main_init();
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> x >> y >> z;
        dist[x][y] = z;
    }
    hamilton();
    afisare();
    return 0;
}