#include <fstream>
#include <vector>
#define INF 1e9
using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");

int n,DP[18][1<<18],A[18][18],m;
bool viz[18][1<<18];
vector<int> V[18];

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

    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
            A[i][j] = INF;

    for (int i=1;i<=m;i++)
    {
        int x,y,c;
        f>>x>>y>>c;
        A[x][y] = c;
        V[y].push_back(x);
    }

    int mx = (1<<n)-1;

    for (int i=0;i<=mx;i++)
        for (int j=0;j<n;j++)
            DP[j][i] = INF;

    DP[0][1] = 0;

    for (int i=0;i<=mx;i++)
    {
        for (int j=0;j<n;j++)
        {
            if (i & (1<<j))
            {
                for (int J=0;J<V[j].size();J++)
                    if (i & (1<<V[j][J]))
                        DP[j][i] = min(DP[j][i], DP[V[j][J]][i ^ (1<<j)] + A[V[j][J]][j]);
            }
        }
    }

    int mn = INF;
    for (int i=0;i<V[0].size();i++)
    {
        mn = min(mn, DP[V[0][i]][(1<<n)-1] + A[V[0][i]][0]);
    }

    if (mn == INF)
        g<<"Nu exista solutie\n";
    else
        g<<mn;

    return 0;
}