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

using namespace std;

const int INF = 0x3f3f3f3f;
const int MAX_N = 20, MAX_CONF = (1 << 18) + 2;

vector < int > v[20];
int cost[MAX_N][MAX_N], d[MAX_CONF][MAX_N];

int main()
{
    ifstream f("hamilton.in");
    ofstream g("hamilton.out");
    int n, m; f >> n >> m;
    memset(cost, INF, sizeof(cost));
    memset(d, INF, sizeof(d));
    for(int i = 1, a, b, c; i <= m; i++)
    {
        f >> a >> b >> c;
        v[b].push_back(a);
        cost[a][b] = cost[b][a] = c;
    }

    d[1][0] = 0;
    for(int conf = 1; conf <= (1 << n) - 1; conf++)
        for(int bit = 0; bit < n; bit++)
            if(conf & (1 << bit))
            {
                for(int j = 0; j < v[bit].size(); j++)
                    if(conf & (1 << v[bit][j]))
                    {
                        d[conf][bit] = min(d[conf][bit], d[conf ^ (1 << bit)][v[bit][j]] + cost[v[bit][j]][bit]);
                    }
            }

    int ans = INF;
    for(int i = 0; i < v[0].size(); i++)
        ans = min(ans, d[(1 << n) - 1][v[0][i]] + cost[v[0][i]][0]);

    if(ans == INF)
        g << "Nu exista solutie";
    else
        g << ans;
    g << '\n';
    f.close();
    g.close();
    return 0;
}