#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int INF = (1 << 28);

//INDEXAT DE LA 0
class graf
{
    public:
        graf(int n)
        {
            this->n = n;
            vecini.resize(n);
            cost.resize(n, vector<int>(n, INF));
        }
        void AddEdge(int x, int y, int cost)
        {
            vecini[y].push_back(x);
            this->cost[x][y] = cost;
        }
        int GetCost()
        {
            vector<vector<int> > dp(1 << n, vector<int>(n, INF));
            dp[1][0] = 0;

            for(int i = 1; i < (1 << n); ++i)
                for(int j = 0; j < n; ++j)
                    if((i & (1 << j)) != 0)
                        for(auto v:vecini[j])
                            if((i & (1 << v)) != 0)
                                dp[i][j] = min(dp[i][j], dp[i - (1 << j)][v] + cost[v][j]);
            int ret = INF;
            for(auto v:vecini[0])
                ret = min(ret, dp[(1 << n) - 1][v] + cost[v][0]);
            return ret;
        }
    private:
        int n;
        vector<vector<int> > vecini;
        vector<vector<int> > cost;
};

int main()
{
    ifstream in("hamilton.in");
    int n, m;
    in >> n >> m;
    int x, y, c;
    graf gr(n);
    while(m--)
    {
        in >> x >> y >> c;
        gr.AddEdge(x, y, c);
    }
    in.close();

    ofstream out("hamilton.out");
    int rasp = gr.GetCost();
    if(rasp == INF)
        out << "Nu exista solutie";
    else
        out << rasp;
    out.close();
    return 0;
}