#include <iostream>
#include <fstream>
#include <vector>
#define INF 2000000000

using namespace std;

int n, m, sol;
int cost[32][32];
int dp[(1<<18)+10][20];
vector <int> G[32];

/// dp[conf][v] = costul minim al unui ciclu care incepe cu nodul 0, se termina in nodul v si contine nodurile
/// specifice reprezentarii in baza 2 a lui conf

inline void Read()
{
    ifstream f ("hamilton.in");
    f>>n>>m;
    int x, y, c, i;
    for (i=1; i<=m; i++)
    {
        f>>x>>y>>c;
        G[x].push_back(y);
        cost[x][y] = c;
    }
    f.close();
}

inline void Solve()
{
    int i, conf, lim;
    lim = (1<<n);
    for (conf = 0; conf < lim; conf++)
        for (i=0; i<n; i++)
            dp[conf][i] = INF;
    dp[1][0] = 0;

    vector <int>::iterator it;

    for (conf = 0; conf < lim; conf++)
    {
        for (i=0; i<=n; i++)
        {
            if ((conf & (1<<i)) != 0)
            {
                for (it = G[i].begin(); it!=G[i].end(); it++)
                {
                    if ((conf & (1<<(*it))) == 0)
                    {
                        dp[conf | (1<<(*it))][*it] = min(dp[conf | (1<<(*it))][*it], dp[conf][i] + cost[i][*it]);
                    }
                }
            }
        }
    }
    sol = INF;
    for (i=1; i<n; i++)
    {
        if (cost[i][0])
            sol = min(sol, dp[lim-1][i] + cost[i][0]);
    }
}

inline void Write()
{
    ofstream g("hamilton.out");
    sol!=INF?g<<sol<<"\n":g<<"Nu exista solutie\n";
    g.close();
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}