#include <iostream>
#include <vector>
#include <fstream>
#include <limits.h>

using namespace std;

//CLASA DE BAZA GRAF

class Graph{

//DATELE MEMBRE

protected:
    int m_number_of_nodes;
    //numarul de noduri


//METODELE

public:

    //functia de citire virtuala -> implementata diferit in fiecare dintre clase
    virtual void read_graph(char *file);
    //parcurgerea in latime
    virtual vector<int> BFS(int node);
    //parcurgerea in adancime
    virtual void DFS(int node, vector<int>& visited);
};

void Graph::read_graph(char *file) {
    return;
}

vector<int> Graph::BFS(int node){
    vector<int> aux;
    return aux;
}

void Graph::DFS(int node, vector<int> &visited) {
    return;
}

//CLASA GRAF ORIENTAT

class Oriented_graph:public Graph{
protected:
    vector< vector<int> > m_adjancency_list;
};

class Oriented_graph_with_costs:Oriented_graph{
private:
    vector< vector<int> > m_costs_matrix;
public:
    void read_graph(char *file);
    int hamilton();
};

void Oriented_graph_with_costs::read_graph(char *file) {
    ifstream f(file);

    vector<int> aux;

    int number_of_edges;

    //citim numarul de noduri si numarul de muchii
    f >> m_number_of_nodes >> number_of_edges;

    //initializam matricea de costuri si matricea de adiacenta

    m_adjancency_list.assign(m_number_of_nodes + 1, aux);

    aux.assign(m_number_of_nodes + 1, INT_MAX);
    m_costs_matrix.assign(m_number_of_nodes + 1, aux);


    //citim fiecare muchie si costul acesteia si o introducem in graf
    for(int i = 0; i < number_of_edges; i++){

        int x, y, c;

        f >> x >> y >> c;
        m_adjancency_list[y].push_back(x);
        m_costs_matrix[x][y] = c;
    }
}

int Oriented_graph_with_costs::hamilton() {

    vector< vector<int> > minimum_costs;
    vector<int> aux;

    //initializam matricea cu costuri minime ale drumurilor de la un nod la altul -> avem atatea linii
    // cate variante de drumuri putem avea, adica atatea linii cate numere in baza 2 cu nr_noduri cifre putem scrie.
    // avem atatea coloane cate noduri sunt

    aux.assign(m_number_of_nodes + 1, INT_MAX);
    minimum_costs.assign(1 << m_number_of_nodes, aux);

    //initializam lantul format dintr-un singur nod cu cost 0
    minimum_costs[1][0] = 0;

    //formam matricea costurilor minime posibile ale tuturor drumurilor posibile - parcurgem toate drumurile posibile si,
    //pentru fiecare nod, verificam daca acel nod se afla in drumul curent sau nu, caz in care trebuie sa actualizam costul minim al lantului
    //care ajunge in acel nod

    for(int i = 0; i < 1 << m_number_of_nodes; i++){

        for(int j = 0; j < m_number_of_nodes; j++){

            //pentru fiecare drum, parcurgem toate nodurile grafului si, pentru nodurile care fac parte din drum, incercam sa actualizam costurile minime ale drumurilor pana la j prin i

            //i este drumul; j este nodu; daca j face parte din i, atunci bitul de pe pozitia j din i este 1
            if( i & (1 << j) ){

                //daca nodul j face parte din drumul curent i, parcurgem vecinii nodului j si, daca vecinul face parte si el din drum, atunci incercam sa actualizam costul minim al drumului
                //pana la nodul j prin drumul i

                for(long k = 0; k < m_adjancency_list.size(); k++){

                    if( i & (1 << m_adjancency_list[j][k]) ){

                        //daca vecinul nodului apartine drumului, verificam daca e cazul sa actualizam minimul costurilor drumurilor pana la nodul j prin drumul i
                        //cu suma dintre costul minim pana la vecin + costul muchiei de la vecin la j

                        minimum_costs[i][j] = min( minimum_costs[i][j], minimum_costs[i ^ (1 << j) ][ m_adjancency_list[j][k] ] + m_costs_matrix[ m_adjancency_list[j][k] ][j]);
                    }
                }
            }
        }
    }

    //aflam costul minim al unnui ciclu
    int mini = INT_MAX;

    for(long i = 0; i < m_adjancency_list[0].size(); i++){
        mini = min(mini, minimum_costs[ (1 << m_number_of_nodes) - 1 ][ m_adjancency_list[0][i] ] + m_costs_matrix[ m_adjancency_list[0][i] ][0]);
    }

    //daca mini a ramas infinit, inseamna ca graful nu este hamiltonian

    if(mini == INT_MAX) return -1;

    return mini;
}

int main() {
    ofstream out("../hamilton.out");

    Oriented_graph_with_costs g;
    int hamilton;

    g.read_graph("../hamilton.in");
    hamilton = g.hamilton();

    if(hamilton == -1) out << "Nu exista solutie";
    else out << hamilton;
    
    return 0;
}