#include <iostream>
#include <algorithm>
#include <fstream>
#include <cmath>
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");

#define INF 1e9

const int maxn = 18;
int c[maxn+2][maxn+2];
int dp[1<<maxn][maxn+2];
int n, m;

int check_if_in_mask( int mask, int bit )
{
    if( (mask & (1<<bit)) == 0 )
        return false;
    else
        return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    f.tie(nullptr);
    g.tie(nullptr);

    f >> n >> m;
    for( int i = 0; i < n; i++ )
        for( int j = 0; j < n; j++ )
            c[i][j] = INF;

    for( int i = 0; i < (1<<18); i++ )
    {
        for( int j = 0; j < n; j++ )
            dp[i][j] = INF;
    }

    for( int i = 0; i < m; i++ )
    {
        int x, y, z;
        f >> x >> y >> z;
        c[x][y] = z;
    }
    dp[1][0] = 0;
    for( int mask = 0; mask < (1<<18); mask++ )
    {
        for( int i = 0; i < n; i++ )
        {
            for( int j = 0; j < n; j++ )
            {
                if( c[i][j] != INF && check_if_in_mask(mask, i) == true && check_if_in_mask(mask, j) == false )
                {
                    int newmask = (mask | (1<<j));
                    dp[newmask][j] = min( dp[newmask][j], dp[mask][i] + c[i][j] );
                }
            }
        }
    }
    int minn = INF;
    for( int i = 0; i < n; i++ )
    {
        minn = min( minn, dp[(1<<n)-1][i] + c[i][0] );
    }
    if( minn == INF )
        g << "Nu exista solutie";
    else
        g << minn;
    return 0;
}