#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;
    for(int i = 0; i < n; i++)
     dp[(1<<i)][i]= 0;

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


                    if((i&(1<<nod)))
                        if(dp[i][nod]+p[nod][j] < dp[(i|(1<<j))][j])
                            dp[(i|(1<<j))][j] = dp[i][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;
}