//bkt - 20p
#include <fstream>
#include <cstring>
#define INF 100000000
#define Nmax 20

using namespace std;

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

int a[Nmax][Nmax], v[Nmax];;
int n, m, min1;
int x, y, c;
bool uz[Nmax];

void bkt(int k)
{
    if(k > n)
        {
            int ans = a[v[n]][v[1]];
        for (int i = 1; i < n; ++i)
            ans += a[v[i]][v[i+1]];
           min1=min(min1, ans);
          /* for ( int i = 1; i <= n; i ++ )
           {
               g << v[i] << " ";
           }
           g << '\n';*/

        }
    else
        {
            for ( int i = 0; i < n; i ++ )
            {
                if(uz[i] == 1) continue;
                uz[i]=1;
                v[k]=i;
                bkt(k+1);
                uz[i]=0;
            }

        }
}

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

    for (int i = 0; i < n; i ++ )
     for (int j = 0; j < n; j ++ )
         a[i][j] = INF;
    min1=INF;
    for ( int i = 1; i <= m; i ++ )
    {
        f >> x >> y >> c;
        a[x][y] = c;
    }
    bkt(1);
    if(min1 == INF) g << "Nu exista solutie";
    else g << min1;
    return 0;
}

/*
#include <fstream>

using namespace std;

const int INF = 100000000;
const int MAXN = 20;

int N, M, Sol;
int P[MAXN], U[MAXN];
int C[MAXN][MAXN];

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
void back(int k)
{
    if (k > N)
    {
        int res = C[P[N]][P[1]];

        for (int i = 1; i < N; ++i)
            res += C[P[i]][P[i+1]];

        Sol = min(Sol, res);
        for ( int i = 0; i <= N; i ++ )
           {
               fout << P[i] << " ";
           }
           fout << '\n';

        return;
    }

    for (int i = 0; i < N; ++i)
        if (!U[i])
        {
            U[i] = 1;
            P[k] = i;
            back(k+1);
            U[i] = 0;
        }
}

int main()
{


    fin >> N >> M;

    Sol = INF;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j) C[i][j] = INF;

    for (int i = 1; i <= M; ++i)
    {
        int x, y;
        fin >> x >> y;
        fin >> C[x][y];
    }

    back(1);

    if (Sol == INF) fout << "Nu exista solutie" << endl;
    else fout << Sol << endl;

    return 0;
}*/