#include <fstream>
#include <vector>
#define INF 1000004
#define put 262150
using namespace std;

ifstream fi("hamilton.in");
ofstream fo("hamilton.out");

vector <int> G[20];

int cost[20][20], dp[put][20], n, m, x, y, c;

int main()
{
    fi>>n>>m;
    for(int i=0; i< (1<<n); i++)
        for(int j=0; j< n; j++)   ///de ce e pana la n si...
            dp[i][j]=INF;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cost[i][j]=INF;
    for(int i=1; i<=m; i++)
    {
        fi>>x>>y>>c;
        cost[x][y]=c;
        G[y].push_back(x);
    }
    //
    dp[1][0] = 0;
    for(int i=0; i < (1<<n); ++i)
        for(int j=0; j < n; ++j)
            if(i & (1<<j))
                for(int k=0; k < G[j].size(); ++k)
                    if(i&(1<<G[j][k]))
                        dp[i][j] = min(dp[i][j], dp[i^(1<<j)][G[j][k]] + cost[G[j][k]][j]);   ///drumul vechi cu un drum nou cu
                                                                                              /// nod intermediar
    int Sol = INF;
    for (int i = 0; i<G[0].size(); ++i)
        Sol = min(Sol, dp[(1<<n)-1][G[0][i]] + cost[G[0][i]][0]);
    if (Sol == INF)
        fo << "Nu exista solutie\n";
    else
        fo << Sol;
    return 0;
}