#include <fstream>

using namespace std;
ifstream cin ("hamilton.in");
ofstream cout ("hamilton.out");
int n, m, sol = 999999999;
bool ok = true;
pair <int, int> v[20][324];
int s[2097155][25];

void solve(unsigned int p, int x, int marafeti)
{
    if(s[p][x] <= marafeti && s[p][x] != 0)
        return;

    s[p][x] = marafeti;

    if(ok == false)
    {
        p &= ~(1 << (x - 1));

        if(p != 0 && x == 1)
            return;
    }

    ok = false;

    if(p == 0)
    {
        sol = min(sol, marafeti);
        return;
    }

    for(int i = 1; i <= v[x][0].first; ++i)
        if((p >> (v[x][i].first - 1)) & 1 == true)
            solve(p, v[x][i].first, marafeti + v[x][i].second);
}

int main()
{
    cin >> n >> m;

    for(int i = 1; i <= m; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;

        if(a == 0)
            a = n;

        if(b == 0)
            b = n;

        v[a][++v[a][0].first].first = b;
        v[a][v[a][0].first].second = c;
    }

    solve((1 << (n)) - 1, 1, 0);

    if(sol != 999999999)
        cout << sol << '\n';
    else
        cout << "Nu exista solutie\n";

    return 0;
}