#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <algorithm>
#include <climits>

using namespace std;

ifstream in("hamilton.in");
ofstream out("hamilton.out");
//in functie de problema
struct edge{
    int cost,x,y;
};

//functii cmp pt sortare
bool cmp_edge(const edge &a,
              const edge &b)
{
    return (a.cost < b.cost);
}

bool cmp(const pair<int,int> &a,
         const pair<int,int> &b)
{
    return (a.second > b.second);
}



class Graf{
public:
    Graf(){}
    //rezolvari probleme
    void bfs();
    void dfs();
    void sorttop();
    void havelHakimi();
    void ctc_Kosoraju();
    void dijkstra();
    void disjoint();
    void kruskal();
    void bellmanFord();
    void diamArb();
    void floydWarshall();
    void cicluEuler();
    void cicluHamiltonian();

private:
    //metode auxiliare
    int find(int x, vector<int> &m_rank, vector<int> &m_parent);
    void union_(int x, int y, vector<int> &m_rank, vector<int> &m_parent);
    void r_dfs(int q, int s, int &m_aux, vector<int> &m_stiva);
    void rr_dfs(int q, vector<vector<int>> &tC, int &nrTc);
    void sorttop_recursie(int q, vector<int> &m_ordtop, int &m_aux);
    void eulerRec(int q, vector<int> &res, vector<vector<int>> &m_list);


private:
    //date
    int m_nrMuchii;
    int m_nrNoduri;
    vector<vector<int>> m_list;
    vector<int> m_viz;

};



int main() {
    Graf graf;
    graf.cicluHamiltonian(); // in functie de problema

}


void Graf::bfs()
{
    vector<int> m_q;
    int m_start;
    in>>m_nrNoduri>>m_nrMuchii>>m_start;
    for(int i=0;i<=m_nrNoduri;i++)
        m_list.push_back({});
    for(int i=0;i<m_nrMuchii;i++)
    {
        int x,y;
        in>>x>>y;
        m_list[x].push_back(y);
    }
    m_viz.push_back(2000000000);
    m_q.push_back(0);
    for(int i=1;i<=m_nrNoduri;i++)
    {
        m_viz.push_back(2000000000);
        m_q.push_back(0);
    }

    m_viz[m_start]=0;
    m_q[1] = m_start;
    int p=1;
    int u=1;
    while(p<=u) //<=
    {
        int r=m_q[p];
        for(int i=0;i<(m_list[r].size());i++)
        {
            int e=m_list[r][i];
            // cout<<e<<' ';

            if(m_viz[r]+1<m_viz[e])
            {
                m_viz[e]=m_viz[r]+1;
                u++;
                m_q[u]=e;


            }
        }
        p++;
    }
    for(int i=1;i<=m_nrNoduri;i++)
    {
        if(m_viz[i]!=2000000000)
            out<<m_viz[i]<<' ';
        else
            out<<"-1 ";
    }
}

void Graf::r_dfs(int q, int s, int &m_aux, vector<int> &m_stiva)
{
    if(s>m_aux)
        m_aux = s;
    m_viz[q]=1;
    for(int i=0;i<m_list[q].size();i++)
    {

        int r=m_list[q][i];

        if(m_viz[r]==0)
        {
            r_dfs(r, s+1, m_aux,m_stiva);

        }


    }
    m_stiva.push_back(q);
}

void Graf::rr_dfs(int q, vector<vector<int>> &tC, int &nrTC) //recursie dfs pt tare conexe
{
    m_viz[q]=1;
    for(int i=0;i<m_list[q].size();i++)
    {

        int r=m_list[q][i];

        if(m_viz[r]==0)
        {
            rr_dfs(r, tC, nrTC);
        }
    }
    tC[nrTC].push_back(q);
}

void Graf::dfs()
{
    vector<int> m_stiva;
    int m_aux = 0;
    in>>m_nrNoduri>>m_nrMuchii;
    for(int i=0;i<=m_nrNoduri;i++)
        m_list.push_back({});
    for(int i=0;i<m_nrMuchii;i++)
    {
        int x,y;
        in>>x>>y;
        m_list[x].push_back(y);
        m_list[y].push_back(x);
    }
    int disp;
    int s=0;
    for(int i=0;i<=m_nrNoduri;i++)
        m_viz.push_back(0);
    for(int i=1;i<=m_nrNoduri;i++)
    {
        if(m_viz[i]==0)
        {
            r_dfs(i,disp, m_aux, m_stiva);
            s++;
        }
    }
    r_dfs(1,disp,m_aux, m_stiva);
    out<<s<<'\n';
}

void Graf::sorttop_recursie(int q, vector<int> &m_ordtop, int &m_aux)
{
    int i;
    m_viz[q]=1;

    for(i=0;i<m_list[q].size();i++)
    {
        int t=m_list[q][i];
        if(m_viz[t]==0)
        {
            sorttop_recursie(t, m_ordtop, m_aux);

        }

    }
    m_aux++;
    m_ordtop[m_aux]=q;
}

void Graf::sorttop()
{
    int m_aux = 0;
    vector<int> m_ordtop;
    vector<int> m_grad;
    int i;
    in>>m_nrNoduri>>m_nrMuchii;
    for(int i=0;i<=m_nrNoduri;i++)
        m_list.push_back({});
    for(i=0;i<m_nrNoduri;i++)
    {
        m_viz.push_back(0);
        m_grad.push_back(0);
        m_ordtop.push_back(0);
    }
    for(i=1;i<=m_nrMuchii;i++)
    {
        int x,y;
        in>>x>>y;
        m_list[x].push_back(y);
        m_grad[y]++;
    }
    for(i=1;i<=m_nrNoduri;i++)
    {
        if(m_grad[i]==0 && m_viz[i]==0)
        {
            sorttop_recursie(i, m_ordtop, m_aux);
        }
    }
    //cout<<w<<'\n';
    for(i=m_aux;i>0;i--)
    {
        out<<m_ordtop[i]<<' ';
    }
}

void Graf::havelHakimi()
{
    vector<pair<int,int>> m_nodGrad;
    int s=0;
    in>>m_nrNoduri;
    for(int i=0;i<=m_nrNoduri;i++)
        m_list.push_back({});
    for(int i=1;i<=m_nrNoduri;i++)
    {
        int x;
        in>>x;
        s+=x;
        m_nodGrad.push_back(make_pair(i,x));
        sort(m_nodGrad.begin(), m_nodGrad.end(),cmp);
    }

    if(s%2==0)
    {
        for(int i=1;i<=m_nrNoduri;i++)
        {
            if(m_nodGrad[i-1].second <= m_nrNoduri - i)
            {
                int aux = m_nodGrad[i-1].second;
                for(int j = 1; j <= aux; j++)
                {
                    m_nodGrad[i+j-1].second--;
                    m_nodGrad[i-1].second--;
                    m_list[m_nodGrad[i-1].first].push_back(m_nodGrad[i+j-1].first);
                    m_list[m_nodGrad[i+j-1].first].push_back(m_nodGrad[i-1].first);
                }
            }
            else
            {
                out<<"-1";
                return;
            }
            sort(m_nodGrad.begin()+i, m_nodGrad.end(),cmp);

        }
        int ok = 1;
        for(int i=0;i<m_nrNoduri;i++)
        {
            if(m_nodGrad[i].second != 0)
                ok = 0;
        }
        if(ok==1)
        {
            for(int i = 1; i <= m_nrNoduri; i++)
            {
                out<<i<<": ";
                for(int j = 0; j < m_list[i].size(); j++)
                {
                    out<<m_list[i][j]<<' ';
                }
                out<<'\n';
            }
        }
        else
        {
            out<<"-1";
            return;
        }

    }
    else
    {
        out<<"-1";
        return;
    }
}

void Graf::ctc_Kosoraju() //tare conexe
{
    vector<int> m_stiva;
    int m_aux = 0;
    int nrTC=0;
    vector<vector<int>> tareConexe;
    vector<vector<int>> listAux;
    int disp;
    in>>m_nrNoduri>>m_nrMuchii;
    for(int i=0;i<=m_nrNoduri;i++)
        m_list.push_back({});
    for(int i=0;i<=m_nrNoduri;i++)
    {
        m_viz.push_back(0);
        listAux.push_back({});
        tareConexe.push_back({});
    }
    for(int i=0;i<m_nrMuchii;i++)
    {
        int x,y;
        in>>x>>y;
        m_list[x].push_back(y);
        listAux[y].push_back(x);
    }
    for(int i=1;i<=m_nrNoduri;i++)
    {
        if(m_viz[i]==0)
        {
            r_dfs(i,disp,m_aux, m_stiva);
        }

    }
    for(int i=1;i<=m_nrNoduri;i++)
    {
        m_list[i].clear();
        for(int j=0;j<listAux[i].size();j++)
        {
            m_list[i].push_back(listAux[i][j]);
        }
    }

    for(int i=0; i<=m_nrNoduri;i++)
        m_viz[i]=0;
    for(int i=m_stiva.size()-1;i>=0;i--)
    {
        if(m_viz[m_stiva[i]]==0)
        {
            nrTC++;
            rr_dfs(m_stiva[i], tareConexe, nrTC);
        }


    }
    out<<nrTC<<'\n';
    for(int i = 1; i <= nrTC; i++)
    {
        for(int j = 0; j < tareConexe[i].size();j++)
            out<<tareConexe[i][j]<<' ';
        out<<'\n';
    }


}

void Graf::dijkstra()
{
    vector<int> m_q;
    set< pair<int,int> > s;
    vector<vector<int>> v;
    vector<vector<int>> d;
    int contor = 0;
    in>>m_nrNoduri>>m_nrMuchii;
    for(int i=0;i<=m_nrNoduri;i++)
    {
        m_viz.push_back(0);
        m_list.push_back({});
        v.push_back({});
        d.push_back({});
    }
    m_q.push_back(0);
    m_q.push_back(0);
    for(int i=2;i<=m_nrNoduri;i++)
    {
        m_q.push_back(1<<30);

    }
    for(int i=1;i<=m_nrMuchii;i++)
    {
        int x,y,z;
        in>>x>>y>>z;
        v[x].push_back(y);
        d[x].push_back(z);
    }
    s.insert(make_pair(0,1));
    contor++;
    while(contor>0)
    {
        int w,q;
        w=s.begin()->first;
        q=s.begin()->second;
        if(m_viz[q]==1)
        {
            s.erase(s.begin());
            contor--;
        }
        else
        {
            m_viz[q]=1;
            int minim=1<<30;
            for(int i=0;i<v[q].size();i++)
            {
                if(m_q[v[q][i]]>m_q[q]+d[q][i])
                {

                    m_q[v[q][i]]=m_q[q]+d[q][i];
                    s.insert(make_pair(m_q[v[q][i]],v[q][i]));
                    contor++;

                }

            }
        }

    }
    for(int i=2;i<=m_nrNoduri;i++)
    {
        if(m_q[i]==1<<30)
            out<<"0 ";
        else
            out<<m_q[i]<<' ';
    }

}
void Graf::disjoint() {

    vector<int> m_rank;
    vector<int> m_parent;

    int n,m;
    in>>n>>m;
    for(int i=0; i<=n;++i) //parent 0 = 0 redundant(nu avem nod 0)
    {
        m_parent.push_back(i);
        m_rank.push_back(0);
    }

    for(int i=1;i<=m;++i)
    {
        int c,x,y; //cerinta,x,y
        in>>c>>x>>y;
        if(c==1)
        {
            this->union_(x, y, m_rank, m_parent);
        }
        if(c==2)
        {
            if(this->find(x, m_rank,m_parent) == this->find(y, m_rank, m_parent))
                out<<"DA\n";
            else
                out<<"NU\n";
        }


    }
}

int Graf::find(int x, vector<int> &m_rank, vector<int> &m_parent) {
    if(m_parent[x] != x)
        m_parent[x] = find(m_parent[x], m_rank, m_parent);
    return m_parent[x];
}

void Graf::union_(int x, int y, vector<int> &m_rank, vector<int> &m_parent) {
    // gasesc reprezentantul multimii pt x si y
    int repx = find(x, m_rank, m_parent);
    int repy = find(y, m_rank, m_parent);
    if(repx == repy) return; //deja in aceeasi multime

    if(m_rank[repx] < m_rank[repy]) //leg multimea mai mica de multimea mai mare
        m_parent[repx] = repy;
    else if(m_rank[repy] < m_rank[repx])
        m_parent[repy] = repx;
    else                            //daca sunt egale leg y de x si rank x creste
    {
        m_parent[repy] = repx;
        m_rank[repx]++;
    }


}

void Graf::kruskal() {
    in>>m_nrNoduri>>m_nrMuchii;
    vector<int> m_rank;
    vector<int> m_parent;
    vector<edge> muchii,raspuns;
    int costTotal = 0;
    for(int i=0; i<=m_nrNoduri;++i) //parent 0 = 0 redundant(nu avem nod 0)
    {
        m_parent.push_back(i);
        m_rank.push_back(0);
    }

    for(int i=0;i<m_nrMuchii;i++)
    {
        int x,y,c;
        in>>x>>y>>c;
        edge aux;
        aux.x = x;
        aux.y = y;
        aux.cost = c;
        muchii.push_back(aux);
    }
    sort(muchii.begin(),muchii.end(),cmp_edge);
    for(int i=0;i<m_nrMuchii;++i)
    {
        if(this->find(muchii[i].x, m_rank, m_parent) != this->find(muchii[i].y, m_rank, m_parent))
        {
            raspuns.push_back(muchii[i]);
            costTotal += muchii[i].cost;
            union_(muchii[i].x, muchii[i].y, m_rank, m_parent);
        }

    }
    out<<costTotal<<'\n'<<raspuns.size()<<'\n';
    for (int i = 0; i < raspuns.size(); ++i) {
        out<<raspuns[i].x<<' '<<raspuns[i].y<<'\n';
    }
}

void Graf::bellmanFord() {
    vector<edge> muchii;
    vector<int> m_distance;
    vector<int> m_parent;

    in>>m_nrNoduri>>m_nrMuchii;

    for(int i=0;i<m_nrMuchii;++i)
    {
        int x,y,c;
        in>>x>>y>>c;
        edge aux;
        aux.x = x;
        aux.y = y;
        aux.cost = c;
        muchii.push_back(aux);
    }
    for(int i = 0; i <= m_nrNoduri; ++i)
    {
        m_parent.push_back(-1);
        m_distance.push_back(INT_MAX);
    }
    m_distance[1] = 0; //1 e nodul de plecare

    for(int i=0; i < m_nrNoduri-1; ++i)
    {
        for(int j=0; j<m_nrMuchii; ++j) //actualizam distantele in O(n*m)
        {
            if(m_distance[muchii[j].x] != INT_MAX &&  m_distance[muchii[j].x] + muchii[j].cost < m_distance[muchii[j].y])
            {
                m_distance[muchii[j].y] = m_distance[muchii[j].x] + muchii[j].cost;
                m_parent[muchii[j].y] = muchii[j].x;
            }
        }
    }
    for(int j=0; j<m_nrMuchii; ++j) //actualizam distantele in O(n*m)
    {
        if(m_distance[muchii[j].x] + muchii[j].cost < m_distance[muchii[j].y])
        {
            out<<"Ciclu negativ!";
            return;
        }
    }
    for(int i=1;i<m_nrNoduri;i++)
    {
        out<<m_distance[i+1]<<' ';
    }
    out<<'\n';



}

void Graf::diamArb() {
    vector<int> m_stiva;
    int m_aux = 0;
    vector<int> m_q;
    in>>m_nrNoduri;
    int maxim = 0;
    int nodMax;
    int m_start = 1;
    for(int i=0;i<=m_nrNoduri;i++)
    {
        m_list.push_back({});
        m_viz.push_back(0);
        m_q.push_back(0);
    }
    for(int i=0;i<m_nrNoduri-1;i++)
    {
        int x,y;
        in>>x>>y;
        m_list[x].push_back(y);
        m_list[y].push_back(x);

    }


    for(int i=1;i<=m_nrNoduri;i++)
    {
        m_viz[i]=2000000000;
    }
    m_viz[m_start]=0;
    m_q[1]=m_start;
    int p=1;
    int u=1;
    while(p<=u) //<=
    {
        int r=m_q[p];
        for(int i=0;i<(m_list[r].size());i++)
        {
            int e=m_list[r][i];
            // cout<<e<<' ';

            if(m_viz[r]+1<m_viz[e])
            {
                m_viz[e]=m_viz[r]+1;
                if(m_viz[e] > maxim)
                {
                    maxim = m_viz[e];
                    nodMax = e;
                }
                u++;
                m_q[u]=e;


            }
        }
        p++;
    }
    //cout<<maxim<<' '<<nodMax;
    //dfs din nodMax
    //in>>m_nrNoduri;
    for(int i=0;i<=m_nrNoduri;i++)
        m_viz[i]=0;
    int dist;
    r_dfs(nodMax, dist, m_aux, m_stiva);
    /*for(int i=0;i<m_stiva.size();i++)
        cout<<m_stiva[i]<<' ';*/
    out<<m_aux+1;

}

void Graf::floydWarshall() {
    in>>m_nrNoduri;

    for(int i = 0; i<=m_nrNoduri;i++)
        m_list.push_back({});

    for(int i = 0; i<m_nrNoduri;i++)
        for(int j=0;j<m_nrNoduri;j++)
        {
            int a;
            in>>a;
            m_list[i].push_back(a);
        }

    for(int k=0;k<m_nrNoduri;k++)
    {
        for(int i = 0; i<m_nrNoduri;i++)
        {
            for(int j=0;j<m_nrNoduri;j++)
            {
                if(m_list[i][k] && m_list[k][j] && (m_list[i][j] > m_list[i][k] + m_list[k][j] || !m_list[i][j]) && i!=j)
                    m_list[i][j] = m_list[i][k] + m_list[k][j];
            }
        }
    }

    for(int i = 0; i<m_nrNoduri;i++)
    {
        for(int j=0;j<m_nrNoduri;j++)
            out<<m_list[i][j]<<' ';
        out<<'\n';
    }

}

void Graf::cicluEuler() {

    in>>m_nrNoduri;
    in>>m_nrMuchii;
    int x,y;
    vector<int> result;
    for(int i=0;i<=m_nrNoduri;i++)
    {
        m_list.push_back({});
    }
    for(int i=0;i<m_nrMuchii;i++)
    {
        in>>x>>y;
        m_list[x].push_back(y);
        m_list[y].push_back(x);
    }
    for (int i = 1; i <= m_nrNoduri; ++i)
    {
        if(m_list[i].size() % 2)
        {
            out<<"-1\n";
            return;
        }
    }

    vector<vector<int>> listAux = m_list;
    eulerRec(1, result, listAux);
    for(int i = 0; i<result.size()-1;i++)
        out<<result[i]<<' ';
    out<<'\n';





}

void Graf::cicluHamiltonian() {
    in>>m_nrNoduri>>m_nrMuchii;
    for (int i = 0; i <= m_nrNoduri; ++i)
    {
        m_list.push_back({});
    }
    int cost[20][20];
    vector<vector<int>> dp;

    for (int i = 0; i < m_nrMuchii; ++i)
    {
        int a,b,c;
        in>>a>>b>>c;
        cost[a][b] = c;
        m_list[b].push_back(a);
    }

    for (int i = 0; i < ((1<<m_nrNoduri)+1); ++i)
    {
        dp.push_back({});
    }

    for (int i = 0; i < ((1<<m_nrNoduri)+1); ++i)
    {
        for (int j = 0; j < m_nrNoduri+1; ++j)
        {
            dp[i].push_back(INT_MAX/2);
        }
    }



    dp[1][0] = 0;
    for (int i = 1; i < (1<<m_nrNoduri); ++i)
    {
        for (int j = 0; j < m_nrNoduri; ++j)
        {
            if(i && (1<< j))
            {
                for(auto k : m_list[j])
                {
                    if(i && (1<<k))
                    {
                        dp[i][j] = min(dp[i][j], dp[i ^ (1<<j)][k] + cost[k][j]);
                    }
                }
            }
        }
    }
    int rasp = INT_MAX/2;
    for(auto i : m_list[0])
    {
        rasp = min(rasp, dp[(1 << m_nrNoduri) - 1][i] + cost[i][0]);
    }
    if(rasp == INT_MAX/2)
        out << "Nu exista solutie";
    else
        out << rasp << '\n';

}

void Graf::eulerRec(int q, vector<int> &res, vector<vector<int>> &m_list) {
    while (!m_list[q].empty())
    {
        int next = m_list[q].back();
        m_list[q].pop_back();
        for(auto i = m_list[next].begin(); i!= m_list[next].end(); i++)
        {
            if(*i == q)
            {
                m_list[next].erase(i);
                break;
            }
        }
        eulerRec(next, res, m_list);
    }
    res.push_back(q);

}