#include <bits/stdc++.h>
#define f first
#define s second

using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

const int INF = 0x3f3f3f3f;
int n, m, p[20][20];
vector <int> v[20];
int dp[300000][20];
int main()
{
    fin >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            p[i][j] = INF;
    for(int i = 1; i <= m; i++)
    {
        int a, b, c;
        fin >> a >> b >> c;

        v[b].push_back(a);

        p[a][b] = c;

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


    dp[1][0] = 0;
    for(int i = 1; i < (1<<n); i++)
        for(int j = 0; j < n; j++)
            if((i&(1<<j)))
            {
                for(int k = 0; k < v[j].size(); k++)
                {
                    int nod = v[j][k];


                    if((i&(1<<nod)))
                       dp[i][j] = min(dp[i][j],dp[i^(1<<j)][nod]+p[nod][j]);



                }

            }


        int ans = INF;

        for(int i = 0; i < v[0].size(); i++)
            ans = min(ans, dp[(1<<n)-1][v[0][i]]+ p[v[0][i]][0]) ;
        if(ans != INF)
            fout << ans << '\n';
        else
            fout <<"Nu exista solutie" << '\n';
    return 0;
}