#include <bits/stdc++.h>
#define nmax 100003
#define X get<0>
#define Y get<1>
#define COST get<2>
#define VIZ get<3>

using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

class graf {
/// tema 1
private:
    int n, m;
    vector<int> h[nmax];
    bitset<nmax> viz;

    int k, dist[nmax], nivel[nmax], mic[nmax];
    bool orientat = false;
    vector<int> transpus[nmax];
    vector<int> ctc[nmax];
    queue< pair<int, int> >q;
    stack<int> s;
    stack<int> s_biconex;
    vector<int> cbiconexe[nmax];
    vector< vector<int> > muchii;


    void dfs(int nod);

    void dfsctc(int nod);

    void bfs(int s);

    void dfs_biconex(int nod, int tata);

    void muchii_critice(int nod, int tata, vector< vector<int> >& h2);

public:
    graf()
    {
        n = m = k = 0;
    }

    void set_graf(int noduri, int muchii, bool Orientat);

    void adauga_muchie(int x, int y);

    void adauga_muchie(int x, int y, int cost);

    void adauga_muchie_matr(int x, int y, int cost);

    void componente_conexe();

    void distante(int s);

    void sortare_topologica();

    void componente_tare_conexe();

    void componente_biconexe();

    static void havel_hakimi();

    static vector< vector<int> > criticalConnections(int n, vector< vector<int> >& connections);


/// tema 2 ----------------------------------------------------------------------------------
private:
    vector < tuple < int, int, int, bool > > muchii_cost;
    vector< pair<int, int> > graf_cost[nmax];
    int matr[1003][1003];

    void unionn(int x, int y, vector<int> &t);

    int findd(int x, vector<int> &t);

    int kruskal(int &n, int &m, vector<tuple<int, int, int, bool>> &muchii_cost, vector<int> &t);

    void dijkstra(int &start, vector<int> &d, vector<bool> &in_coada);

    void bellman_ford(bool &circuit, vector<int> &d, queue<int> &coada_noduri, vector<bool>& in_coada, vector<int> &contor);

public:
    void apm();

    void pb_dijkstra(int start);

    void disjoint();

    void pb_bellman_ford(int start);


/// tema 3 ----------------------------------------------------------------------------------
private:
    void dfs_darb(int nod, int dist, vector<int> &d, bitset<nmax> &viz);

    void roy_floyd(vector< vector<int> > &d);

    bool bfs_ford_fulkerson(int start, int dest, vector< vector<int> > &rezidual, vector<int> &t);

    int ford_fulkerson(int start, int dest, vector< vector<int> > &rezidual, vector<int> &t);

public:
    void darb();

    void pb_roy_floyd();

    void maxflow();


/// tema 4 ----------------------------------------------------------------------------------
private:
    vector<int> ciclu_eulerian();

    int ciclu_hamiltonian();

public:
    void pb_ciclueuler();

    void pb_hamilton();
};

void graf :: set_graf(int noduri, int muchii, bool Orientat)
{
    n = noduri;
    m = muchii;
    orientat = Orientat;
}

void graf :: adauga_muchie(int x, int y)
{
    if(orientat)
    {
        h[x].push_back(y);
        transpus[y].push_back(x); // ctc
    }
    else
    {
        h[x].push_back(y);
        h[y].push_back(x);
    }
}

void graf :: adauga_muchie(int x, int y, int cost)
{
    if(orientat)
    {
        graf_cost[x].push_back({y, cost});
    }
    else
    {
        // pentru kruskal
        muchii_cost.push_back({x, y, cost, false});
    }
}

void graf :: adauga_muchie_matr(int x, int y, int cost)
{
    matr[x][y] = cost;
}

void graf :: dfs(int nod)
{
    viz[nod] = 1;
    for(auto i : h[nod])
        if(!viz[i])
            dfs(i);

    // pentru sortarea topologica si ctc
    s.push(nod);
}

void graf :: dfsctc(int nod)
{
    viz[nod] = 1;
    ctc[k].push_back(nod);
    for(auto i : transpus[nod])
        if(!viz[i])
            dfsctc(i);
}

void graf :: bfs(int s)
{
    pair<int, int> nod;
    q.push({s, 0});
    viz[s] = 1;
    dist[s] = 0;

    while(!q.empty())
    {
        nod = q.front();
        dist[nod.first] = nod.second;
        q.pop();

        for(auto i : h[nod.first])
            if(!viz[i])
            {
                q.push({i, nod.second + 1});
                viz[i] = 1;
            }
    }
}

void graf :: componente_conexe()
{
    int nrc;
    nrc = 0;
    for(int i = 1; i <= n; i++)
        if(!viz[i])
        {
            dfs(i);
            nrc++;
        }
    fout << nrc << "\n";
}

void graf :: distante(int s)
{
    for(int i = 1; i <= nmax - 3; i++)
        dist[i] = -1;
    bfs(s);
    for(int i = 1; i <= n; i++)
        fout << dist[i] << " ";
    fout << "\n";
}

void graf :: sortare_topologica()
{
    for(int i = 1; i <= n; i++)
        if(!viz[i])
            dfs(i);

    while(!s.empty())
    {
        fout << s.top() << " ";
        s.pop();
    }
    fout << "\n";
}

void graf :: componente_tare_conexe() // kosaraju
{
    int top;
    for(int i = 1; i <= n; i++)
        if(!viz[i])
            dfs(i);

    viz.reset();
    while(!s.empty())
    {
        top = s.top();
        s.pop();
        if(!viz[top])
        {
            k++;
            dfsctc(top);
        }
    }

    fout << k << "\n";
    for(int i = 1; i <= k; i++)
    {
        for(auto j : ctc[i])
            fout << j << " ";
        fout<<"\n";
    }
}

void graf :: dfs_biconex(int nod, int tata)
{
    viz[nod] = 1;
    s_biconex.push(nod);

    mic[nod] = nivel[nod] = nivel[tata] + 1;

    for(auto i : h[nod])
    {
        if(i != tata)
        {
            if(viz[i])
                mic[nod] = min(mic[nod], nivel[i]);
            else
            {
                dfs_biconex(i, nod);

                mic[nod] = min(mic[nod], mic[i]);

                if(nivel[nod] <= mic[i]) // o noua componenta biconexa
                {
                    k++;
                    while(s_biconex.top() != i)
                    {
                        cbiconexe[k].push_back(s_biconex.top());
                        s_biconex.pop();
                    }
                    s_biconex.pop();
                    cbiconexe[k].push_back(i);
                    cbiconexe[k].push_back(nod);
                }
            }
        }
    }
}

void graf :: componente_biconexe()
{
    nivel[0] = 0;
    dfs_biconex(1, 0);

    fout << k << "\n";
    for(int i = 1; i <= k; i++)
    {
        for(auto j : cbiconexe[i])
            fout << j << " ";
        fout<<"\n";
    }
}

void graf :: havel_hakimi()
{
    int lg, x, suma = 0;
    vector<int>v;
    fin >> lg;
    for(int i = 1; i <= lg; i++)
    {
        fin >> x;
        v.push_back(x);
        suma += x;
    }

    if(suma % 2 == 1)
    {
        fout << "Nu\n";
        return;
    }

    while(true)
    {
        if(v.size() == 0)
        {
            fout << "Da\n";
            return;
        }
        sort(v.begin(), v.end(), greater<int>());
        x = v[0];

        if((int)v.size() - 1 < x)
        {
            fout << "Nu\n";
            return;
        }
        for(int i = 1; i < x + 1; i++)
        {
            v[i]--;
            v[i - 1]= v[i];

            if(v[i] < 0)
            {
                fout << "Nu\n";
                return;
            }
        }
        v.pop_back();
    }
}

/*void graf :: muchii_critice(int nod, int tata, vector< vector<int> >& h2)
{
    viz[nod] = 1;
{1}
    mic[nod] = nivel[nod] = nivel[tata] + 1;
{1}
    for(int i = 0; i < h2[nod].size(); i++)
    {
        int vecin = h2[nod][i];
{1}
        if(!viz[vecin])
        {
            muchii_critice(vecin, nod, h2);
{1}
            mic[nod] = min(mic[nod], mic[vecin]);
{1}
            if(nivel[nod] < mic[vecin])
            {
                vector<int> muchie = {nod, vecin};
                muchii.push_back(vector<int>{nod, vecin});
            }
        }
        else if(vecin != tata)
        {
            mic[nod] = min(mic[nod], nivel[vecin]);
        }
    }
}
{1}
vector<vector<int>> graf :: criticalConnections(int n, vector<vector<int>>& connections)
{
    vector< vector<int> > h2(100003);
    for(int i = 0; i < connections.size(); i++)
    {
        h2[connections[i][0]].push_back(connections[i][1]);
        h2[connections[i][1]].push_back(connections[i][0]);
    }
    muchii_critice(1, 0, h2);
    return muchii;
}*/

///---------------------------------------------------------------------------------------------

void graf :: unionn(int x, int y, vector<int> &t)
{
    t[y] = x;
}

int graf :: findd(int x, vector<int> &t)
{
    int rad, y;
    rad = x;
    while(t[rad] != 0)
        rad = t[rad];

    while(x != rad)
    {
        y = t[x];
        t[x] = rad;
        x = y;
    }
    return rad;
}

int graf :: kruskal(int &n, int &m, vector<tuple<int, int, int, bool>> &muchii_cost, vector<int> &t)
{
    int costmin, nrcc, x, y;
    sort(muchii_cost.begin(), muchii_cost.end(),
        [](const tuple<int, int, int, bool> &A, const tuple<int, int, int, bool> &B) -> bool { return COST(A) < COST(B); });

    nrcc = n;
    costmin = 0;
    for(int i = 0; i < m && nrcc > 1; i++)
    {
        x = findd(X(muchii_cost[i]), t);
        y = findd(Y(muchii_cost[i]), t);
        if(x != y)
        {
            VIZ(muchii_cost[i]) = true;
            costmin += COST(muchii_cost[i]);
            unionn(x, y, t);
            nrcc--;
        }
    }

    return costmin;
}

void graf :: apm()
{
    vector<int> t(nmax);
    for(int i = 0; i <= nmax - 3; i++)
        t[i] = 0;

    fout << kruskal(n, m, muchii_cost, t) << "\n";


    int cnt;
    cnt = 0;
    for(int i = 0; i < m; i++)
        if(VIZ(muchii_cost[i]) == true)
            cnt++;
    fout << cnt << "\n";

    for(int i = 0; i < m; i++)
        if(VIZ(muchii_cost[i]) == true)
            fout << X(muchii_cost[i]) << " " << Y(muchii_cost[i]) << "\n";
}

void graf :: dijkstra(int &start, vector<int> &d, vector<bool> &in_coada)
{
    int k, v, c;
    priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > coada_muchii;
    coada_muchii.push({d[start], start});

    while(!coada_muchii.empty())
    {
        k = coada_muchii.top().second;
        coada_muchii.pop();
        in_coada[k] = false;

        for (auto w : graf_cost[k])
        {
            v = w.first;
            c = w.second;

            if(d[v] > d[k] + c)
            {
                d[v] = d[k] + c;

                if(!in_coada[v])
                {
                    coada_muchii.push({d[v], v});
                    in_coada[v] = true;
                }
            }
        }
    }
}

void graf :: pb_dijkstra(int start)
{
    vector<int> d(nmax);
    vector<bool> in_coada(nmax);

    for (int i = 1; i <= n; i++)
        d[i] = 1e9;
    d[start] = 0; // de la nodul 1 plec

    dijkstra(start, d, in_coada);

    for(int i = 2; i <= n; i++)
        if(d[i] == 1e9) fout << "0 ";
        else fout << d[i] << " ";
    fout << "\n";
}

void graf :: disjoint()
{
    int cod, x, y, a, b;
    vector<int> t(nmax);
    for(int i = 0; i <= nmax - 3; i++)
        t[i] = 0;

    for(int i = 1; i <= m; i++)
    {
        fin >> cod >> x >> y;
        if(cod == 1 && x != y)
        {
            a = findd(x, t);
            b = findd(y, t);
            if(a != b) unionn(a, b, t);
        }
        else if(cod == 2)
        {
            if(findd(x, t) == findd(y, t))
                fout << "DA\n";
            else fout << "NU\n";
        }
    }
}

void graf :: bellman_ford(bool &circuit, vector<int> &d, queue<int> &coada_noduri, vector<bool>& in_coada, vector<int> &contor)
{
    int k, v, c;
    while(!coada_noduri.empty())
    {
        k = coada_noduri.front();
        coada_noduri.pop();
        in_coada[k] = false;

        for(auto w : graf_cost[k])
        {
            v = w.first;
            c = w.second;

            if(d[v] > d[k] + c)
            {
                d[v] = d[k] + c;
                if(!in_coada[v])
                {
                    if(contor[v] > n)
                    {
                        circuit = true;
                        return;
                    }
                    else
                    {
                        coada_noduri.push(v);
                        in_coada[v] = true;
                        contor[v]++;
                    }
                }
            }
        }
    }
}

void graf :: pb_bellman_ford(int start)
{
    bool circuit = false;
    vector<int> d(nmax);
    vector<bool> in_coada(nmax);
    queue<int> coada_noduri;
    vector<int> contor(nmax);

    for (int i = 1; i <= n; i++)
        d[i] = 1e9;
    d[start] = 0; // de la nodul 1 plec

    coada_noduri.push(start);
    in_coada[start] = true;

    bellman_ford(circuit, d, coada_noduri, in_coada, contor);

    if(circuit)
    {
        fout << "Ciclu negativ!\n";
        return;
    }
    for(int i = 1; i <= n; i++)
        if(i != start)
            fout << d[i] << " ";
    fout << "\n";
}

///---------------------------------------------------------------------------------------------

void graf :: dfs_darb(int nod, int dist, vector<int> &d, bitset<nmax> &viz)
{
    viz[nod] = true;
    d[nod] = dist;
    for(auto i : h[nod])
        if(viz[i] == false)
            dfs_darb(i, dist + 1, d, viz);
}

void graf :: darb()
{
    int nod, mx;
    vector<int> d(nmax);
    bitset<nmax> viz;
    for (int i = 1; i <= n; i++)
        d[i] = 0;

    dfs_darb(1, 1, d, viz);
    mx = 0;
    for(int i = 1; i <= n; i++)
        if(viz[i] == true && d[i] > mx)
        {
            nod = i;
            mx = d[i];
        }

    viz.reset();
    dfs_darb(nod, 1, d, viz);

    mx = 0;
    for(int i = 1;i <= n; i++)
        mx = max(mx, d[i]);
    fout << mx << "\n";
}

void graf :: roy_floyd(vector< vector<int> > &d)
{
    for(int k = 0; k < n; k++)
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

void graf :: pb_roy_floyd()
{
    vector< vector<int> > d;
    d.resize(n);
    for(int i = 0; i < n; i++)
    {
        d[i].resize(n);
        for(int j = 0; j < n; j++)
            if(i == j)
                d[i][j] = 0;
            else if(matr[i][j] == 0)
                d[i][j] = 1e9;
            else d[i][j] = matr[i][j];
    }

    roy_floyd(d);

    for(int i = 0; i < n; i++, fout << "\n")
        for(int j = 0; j < n; j++)
            if(d[i][j] == 1e9)
                fout << "0 ";
            else
                fout << d[i][j] << " ";
}

bool graf :: bfs_ford_fulkerson(int start, int dest, vector< vector<int> > &rezidual, vector<int> &t)
{
    queue<int> q;
    vector<bool> viz;
    viz.resize(n, false);

    q.push(start);
    viz[start] = true;
    t[start] = -1;

    while(!q.empty())
    {
        int nod = q.front();
        q.pop();

        for(int i = 0; i < n; i++)
        {
            if(!viz[i] && rezidual[nod][i] > 0)
            {
                if(i == dest)
                {
                    t[i] = nod;
                    return true;
                }
                q.push(i);
                t[i] = nod;
                viz[i] = true;
            }
        }
    }

    return false;
}

int graf :: ford_fulkerson(int start, int dest, vector< vector<int> > &rezidual, vector<int> &t)
{
    int nod, flux_temp, flux = 0;

    while(bfs_ford_fulkerson(start, dest, rezidual, t))
    {
        flux_temp = 1e9;
        nod = dest;
        while(nod != start)
        {
            flux_temp = min(flux_temp, rezidual[t[nod]][nod]);
            nod = t[nod];
        }

        nod = dest;
        while(nod != start)
        {
            rezidual[t[nod]][nod] -= flux_temp;
            rezidual[nod][t[nod]] += flux_temp;
            nod = t[nod];
        }

        flux += flux_temp;
    }

    return flux;
}

void graf :: maxflow()
{
    int flux;
    vector< vector<int> > rezidual;
    vector<int> t(n);

    rezidual.resize(n);
    for(int i = 0; i < n; i++)
    {
        rezidual[i].resize(n);
        for(int j = 0; j < n; j++)
            rezidual[i][j] = matr[i][j];
    }

    flux = ford_fulkerson(0, n - 1, rezidual, t);

    fout << flux << "\n";
}

vector<int> graf :: ciclu_eulerian()
{
    stack<int> st;
    vector<int> sol;

    int nod, v;
    for(int i = 1; i <= n; i++)
        if(h[i].size() % 2 == 1)
        {
            sol.push_back(-1);
            return sol;
        }

    st.push(1);
    while(!st.empty())
    {
        nod = st.top();

        if(h[nod].size() > 0) //daca am vecini, sterg o muchie
        {
            v = h[nod][0];
            h[nod].erase(h[nod].begin());

            for(int w = 0; w < (int)h[v].size(); w++) // sterg pe nod din lista de vecini a lui v
            {
                if(h[v][w] == nod)
                {
                    h[v].erase(h[v].begin() + w);
                    w = h[v].size() + 1; //break;
                }
            }
            st.push(v);
        }
        else
        {
            st.pop();
            sol.push_back(nod);
        }
    }

    return sol;
}

void graf :: pb_ciclueuler()
{
    vector<int> sol;

    sol = ciclu_eulerian();

    if(sol[0] == -1)
    {
        fout << "-1\n";
        return;
    }

    for(int i = 1; i < (int)sol.size(); i++)
        fout << sol[i] << " ";
    fout << "\n";
}

int graf :: ciclu_hamiltonian()
{
    int rez;
    /// dp[i][j] = costul lantului de la 0 la j care contine nodurile din (binar i)
    vector< vector<int> > dp;
    dp.resize((1 << n));
    for(int i = 0; i < (1 << n); i++)
    {
        dp[i].resize(n);
        for(int j = 0; j < n; j++)
            dp[i][j] = 1e9;
    }
    dp[1][0] = 0;

    for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
            if(matr[i][j] == 0)
                matr[i][j] = 1e9;

    for(int i = 0; i < (1 << n); i++)
		for(int j = 0; j < n; j++)
			if((i & (1<<j)) != 0)
                for(int k = 0; k < n; k++)
					if(matr[j][k] != 0 && ((i & (1<<k)) != 0))
						dp[i][j] = min(dp[i][j], dp[i ^ (1<<j)][k] + matr[k][j]);

    rez = 1e9;
	for(int i = 0; i < n; i++)
		rez = min(rez, dp[(1 << n) - 1][i] + matr[i][0]);

    return rez;
}

void graf :: pb_hamilton()
{
    int rez;

    rez = ciclu_hamiltonian();

    if(rez == 1e9)
        fout << "Nu exista solutie\n";
	else
        fout << rez << "\n";
}

graf g;

int main()
{
    /// hamilton
    int n, m, x, y, cost;
    fin >> n >> m;
    g.set_graf(n, m, true);

    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y >> cost;
        g.adauga_muchie_matr(x, y, cost);
    }
    g.pb_hamilton();

    /// ciclueuler
    /*int n, m, x, y;
    fin >> n >> m;
    g.set_graf(n, m, false);

    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        g.adauga_muchie(x, y);
    }
    g.pb_ciclueuler();*/

    /// maxflow
    /*int n, m, x, y, cost;
    fin >> n >> m;
    g.set_graf(n, m, true);

    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y >> cost;
        g.adauga_muchie_matr(x - 1, y - 1, cost);
    }
    g.maxflow();*/

    /// royfloyd
    /*int n, m=0, cost;
    fin >> n;
    g.set_graf(n, m, true);

    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
        {
            fin >> cost;
            g.adauga_muchie_matr(i, j, cost);
        }
    g.pb_roy_floyd();*/

    /// darb
    /*int n, m, x, y;

    fin >> n;
    m = n - 1;
    g.set_graf(n, m, false);

    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        g.adauga_muchie(x,y);
    }
    g.darb();*/

    /// bellmanford
    /*int n, m, x, y, cost;
    fin >> n >> m;
    g.set_graf(n, m, true);

    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y >> cost;
        g.adauga_muchie(x, y, cost);
    }
    g.pb_bellman_ford(1);*/

    /// disjoint
    /*int n, m;
    fin >> n >> m;
    g.set_graf(n, m, false);
    g.disjoint();*/

    /// dijkstra
    /*int n, m, x, y, cost;
    fin >> n >> m;
    g.set_graf(n, m, true);

    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y >> cost;
        g.adauga_muchie(x, y, cost);
    }
    g.pb_dijkstra(1);*/

    /// apm
    /*int n, m, x, y, cost;
    fin >> n >> m;
    g.set_graf(n, m, false);

    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y >> cost;
        g.adauga_muchie(x, y, cost);
    }
    g.apm();*/

    /// dfs
    /*int n, m, x, y;

    fin >> n >> m;
    g.set_graf(n, m, false);

    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        g.adauga_muchie(x,y);
    }
    g.componente_conexe();*/

    /// bfs
    /*int n, m, s, x, y;

    fin >> n >> m >> s;
    g.set_graf(n, m, true);

    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        g.adauga_muchie(x,y);
    }
    g.distante(s);*/

    /// biconex
    /*int n, m, x, y;

    fin >> n >> m;
    g.set_graf(n, m, false);

    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        g.adauga_muchie(x,y);
    }
    g.componente_biconexe();*/

    /// ctc
    /*int n, m, x, y;

    fin >> n >> m;
    g.set_graf(n, m, true);

    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        g.adauga_muchie(x,y);
    }
    g.componente_tare_conexe();*/

    /// sortare topologica
    /*int n, m, s, x, y;

    fin >> n >> m;
    g.set_graf(n, m, true);

    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        g.adauga_muchie(x,y);
    }
    g.sortare_topologica();*/

    /// havel hakimi
    //graf::havel_hakimi();

    /// muchii critice [[0,1],[1,2],[2,0],[1,3]]
    //graf::criticalConnections(..);


    fin.close();
    fout.close();
    return 0;
}