#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct Weigthed_Edge{

    int u,v,weight;

    Weigthed_Edge(int a, int b, int c):u(a),v(b),weight(c){}
    ~Weigthed_Edge() = default;

    bool operator<(const Weigthed_Edge &b) const
    {
        return this->weight<b.weight;
    }
};

class Graph{
private:
    int n;
    vector < vector<int> > la;

    vector<vector<int>> componente_biconexe;
    vector<vector<int>> componente_tconexe;
    vector<int> lowest, level, father, degrees;
    vector<bool> onstack;
    stack<int> S;
    stack<pair<int,int>> edges_biconexe;
    int index;

    void dfs(int nod_crt, vector<bool> &viz);
    void dfs_biconexe(int nod_crt);
    void dfs_tarjan(int nod_crt);
    void add_cmp_biconexa(int x, int y);
    bool consume(int nr, int poz);


public:
    Graph(int nr_noduri):n(nr_noduri), la(nr_noduri+1), componente_biconexe(0), componente_tconexe(0), lowest(0), level(0), father(0), onstack(0), index(0), degrees(0){}
    ~Graph() = default;

    void add_edge(int from, int to){
        la[from].push_back(to);
    }
    void bfs_print_dist(int start=1); // Starting from node 1 by default
    int nr_conexe_dfs();
    void print_sortare_topologica(ostream &out);
    void print_comp_biconexe_udg(ostream &out);
    void print_comp_tconexe_dg(ostream &out);
    bool Havel_Hakimi(vector<int> &grade_noduri);

    void static print_dist_BellmanFord(ostream &out, int start, vector<Weigthed_Edge> &edges, int nn);
    void static print_APM_Kruskal(ostream &out, vector<Weigthed_Edge> &edges, int nn);
    void static solve_disjoint(istream &in, ostream &out);
    void static update_disjoint(int x, vector<int> &father);
};


void Graph::bfs_print_dist(int start)
{
    vector<int> dist(n+1,0);
    queue<int> q;
    int nod_crt;

    q.push(start);
    dist[start]=1;

    while(!q.empty())
    {
        nod_crt = q.front();
        q.pop();
        for(auto nod_vecin: la[nod_crt])
        {
            if(dist[nod_vecin] == 0)
            {
                dist[nod_vecin] = dist[nod_crt] + 1;
                q.push(nod_vecin);
            }
        }
    }

    for(int i=1;i<=n;++i)
        g<<dist[i]-1<<' ';
}

int Graph::nr_conexe_dfs()
{
    vector<bool> viz(n+1, false);
    int nr_c=0;
    for(int i=1;i<=n;++i)
    {
        if(!viz[i])
        {
            ++nr_c;
            dfs(i, viz);
        }
    }

    return nr_c;
}


void Graph::print_sortare_topologica(ostream &out)
{
    queue<int> zero_nodes;
    degrees.resize(n+1,0);
    int nod_curent, i;
    for(i=1;i<=n;++i)
    {
        for(auto nod_vecin: la[i])
            ++degrees[nod_vecin];
    }
    for(i=1; i<=n;++i)
        if(degrees[i] == 0)
            zero_nodes.push(i);
    if(zero_nodes.empty())
    {
        cout<<"Cyclic Graph. Can't sort.";
        return;
    }
    while(!zero_nodes.empty())
    {
        nod_curent = zero_nodes.front();
        zero_nodes.pop();
        out<<nod_curent<<' ';

        for(auto nod_vecin: la[nod_curent])
        {
            --degrees[nod_vecin];
            if(degrees[nod_vecin] == 0)
                zero_nodes.push(nod_vecin);
        }
    }
    degrees.clear();
}

void Graph::dfs(int nod_crt, vector<bool> &viz)
{

    for(auto nod_vecin: la[nod_crt])
    {
        if(!viz[nod_vecin])
        {
            viz[nod_vecin] = true;
            dfs(nod_vecin, viz);
        }
    }

}


void Graph::add_cmp_biconexa(int x, int y)
{
    int a,b;
    vector<int> componenta_biconexa;
    do
    {
        a=edges_biconexe.top().first;
        b=edges_biconexe.top().second;

        edges_biconexe.pop();

        componenta_biconexa.push_back(a);
        componenta_biconexa.push_back(b);

    }while((a!=x || b!=y) && !edges_biconexe.empty());

    sort(componenta_biconexa.begin(), componenta_biconexa.end() );
    componente_biconexe.push_back(componenta_biconexa);
}

void Graph::dfs_biconexe(int nod_crt)
{
    level[nod_crt] = level[father[nod_crt]] + 1;
    lowest[nod_crt] = level[nod_crt];

    for(auto nod_vecin: la[nod_crt])
    {
        if(level[nod_vecin] == 0)
        {
            father[nod_vecin] = nod_crt;
            edges_biconexe.push(make_pair(nod_crt, nod_vecin));

            dfs_biconexe(nod_vecin);

            if(lowest[nod_vecin] >= level[nod_crt])
                add_cmp_biconexa(nod_crt, nod_vecin);

            lowest[nod_crt] = min(lowest[nod_crt], lowest[nod_vecin]);
        }
        else if(nod_vecin!= father[nod_crt])
            lowest[nod_crt] = min(lowest[nod_crt], level[nod_vecin]);;
    }


}

void Graph::print_comp_biconexe_udg(ostream &out)
{
    lowest.resize(n+1, 0);
    level.resize(n+1, 0);
    father.resize(n+1, 0);

    dfs_biconexe(1);

    out<<componente_biconexe.size()<<'\n';
    for(auto componenta:componente_biconexe)
    {
        out<<componenta[0];
        for(int i=1;i<componenta.size();++i)
            if(componenta[i]!=componenta[i-1])
                out<<' '<<componenta[i];
        out<<'\n';
    }

    lowest.clear();
    level.clear();
    father.clear();
}



void Graph::dfs_tarjan(int nod_crt)
{
    ++index;
    level[nod_crt] = index;
    lowest[nod_crt] = index;
    S.push(nod_crt);
    onstack[nod_crt] = true;

    for(auto nod_vecin : la[nod_crt])
    {
        if(level[nod_vecin]==0)
        {
            dfs_tarjan(nod_vecin);
            lowest[nod_crt] = min(lowest[nod_crt], lowest[nod_vecin]);
        }
        else if(onstack[nod_vecin])
            lowest[nod_crt] = min(lowest[nod_crt], level[nod_vecin]);
    }

    if(level[nod_crt] == lowest[nod_crt])
    {
        vector<int> comp_tconexa;
        int st;
        do
        {
            st = S.top();
            S.pop();
            onstack[st]=false;
            comp_tconexa.push_back(st);
        }while(st!=nod_crt);

        componente_tconexe.push_back(comp_tconexa);
    }

}

void Graph::print_comp_tconexe_dg(ostream &out)
{
    onstack.resize(n+1, false);
    lowest.resize(n+1, 0);
    level.resize(n+1, 0);

    for(int i=1;i<=n;++i)
    {
        if(level[i] == 0)
        {
            dfs_tarjan(i);
        }
    }
    out<<componente_tconexe.size()<<'\n';
    for(auto comp: componente_tconexe)
    {
        for(auto nod:comp)
            out<<nod<<' ';
        out<<'\n';
    }
    onstack.clear();
    lowest.clear();
    level.clear();
}


bool Graph::consume(int nr, int poz)
{
    if(nr == 0)
        return true;
    if(poz == 0)
        return false;

    if(nr>degrees[poz])
    {
        bool ok = consume(n-degrees[poz], poz-1);
        degrees[poz-1]+=degrees[poz];
        degrees[poz]=0;
        return ok;
    }

    degrees[poz-1]+=nr;
    degrees[poz]  -=nr;

    return true;
}

bool Graph::Havel_Hakimi(vector<int>& grade_noduri)
{
    int sum=0, max_grade = 0;
    degrees.resize(n, 0);
    for(auto x: grade_noduri)
    {
        if(x>=n)
        {
            degrees.clear();
            return false;
        }

        ++degrees[x];
        sum+=x;

        if(x>max_grade)
            max_grade = x;
    }
    if( sum & 1)
    {
        degrees.clear();
        return false;
    }
    if(max_grade <=1 )
    {
        degrees.clear();
        return true;
    }

    for(int i=max_grade; i; --i)
    {
        while(degrees[i])
        {
            --degrees[i];
            if( !consume(i, i) )
            {
                degrees.clear();
                return false;
            }
        }
    }
    degrees.clear();
    return true;
}


void get_degrees(const char* f_name, vector<int>& v)
{
    ifstream in(f_name);
    int n,m,a,b;
    in>>n>>m;
    v.resize(n, 0);

    for(int i=0;i<m;++i)
    {
        f>>a>>b;
        ++v[a-1];
        ++v[b-1];
    }

}


void Graph::print_dist_BellmanFord(ostream &out, int start, vector<Weigthed_Edge> &edges, int nn)
{
    vector<int> distance(nn+1, 1111);
    distance[start] = 0;

    for(int i=1;i<nn;++i)
    {
        for(auto x: edges)
            if(distance[x.u] + x.weight < distance[x.v])
                distance[x.v] = distance[x.u] + x.weight ;
    }
    for(auto x: edges)
        if(distance[x.u] + x.weight < distance[x.v])
        {
            out<<"Ciclu negativ!";
            return;
        }
    for(int i=1; i<=nn;++i)
        if(i!=start)
            out<<distance[i]<<' ';
}

void Graph::update_disjoint(int x, vector<int> &father)
{
    if(x!=father[x])
        update_disjoint(father[x], father);
    father[x] = father[father[x]];
}

void  Graph::print_APM_Kruskal(ostream &out, vector<Weigthed_Edge> &edges, int nn) // Will print the total cost of the APM, the number of edges
{                                                                                  // and a list of pairs (x, y) representing the chosen edges
    int nr_chosen = 0, i=0, sum=0;
    int x, y;
    vector<pair<int,int>> chosen_edges;
    vector<int> father(nn+1);
    vector<int> height(nn+1,0);

    for(int k=1; k<=nn; ++k)
        father[k] = k;
    sort(edges.begin(), edges.end());

    while(i<edges.size() && nr_chosen<nn-1)
    {
        x = edges[i].u;
        y = edges[i].v;

        update_disjoint(x, father);
        update_disjoint(y, father);

        if(father[x] != father[y]) /// the nodes are not in the same tree so far
        {
            sum += edges[i].weight;
            ++nr_chosen;
            chosen_edges.push_back(make_pair(edges[i].u, edges[i].v)); /// add edge to the list of selected edges

            if(height[father[x]] > height[father[y]])
                father[father[y]] = father[x];
            else if(height[father[y]] > height[father[x]])
                father[father[x]] = father[y];
            else
            {
                father[father[y]] = father[x];
                ++height[father[x]];
            }
            /*
            if(height[x] > height[y])
                father[y] = x;       /// y becomes a part of x's tree and height of x stays the same
            else if(height[x] < height[y])
                father[x] = y;       /// x becomes a part of y's tree and height of y stays the same
            else
            {
                father[y] = x;       /// the tree of root x and the tree of root y have the same height
                ++height[x];         /// either one can become the main root but the height is increased by 1
            }*/
        }

        ++i;
    }

    out<<sum<<'\n'<<nn-1;
    for(auto edge: chosen_edges)
        out<<'\n'<<edge.first<<' '<<edge.second;
}

void Graph::solve_disjoint(istream &in, ostream &out)
{
    int n,m;
    int op, x, y;
    in>>n>>m;

    vector<int> father(n+1);
    vector<int> height(n+1,0);
    for(int k=1; k<=n; ++k)
        father[k] = k;

    for(int i=0;i<m;++i)
    {
        f>>op>>x>>y;
        update_disjoint(x, father);
        update_disjoint(y, father);
        if(op == 1)
        {
            //father[father[y]] = father[x];
            if(height[father[x]] > height[father[y]])
                father[father[y]] = father[x];
            else if(height[father[y]] > height[father[x]])
                father[father[x]] = father[y];
            else
            {
                father[father[y]] = father[x];
                ++height[father[x]];
            }
        }
        else
        {
            if(father[x] == father[y])
                out<<"DA\n";
            else
                out<<"NU\n";
        }
    }
}


int main()
{
    int n,m,x;
    int a,b,c;
    //Graph::solve_disjoint(f,g);

    f>>n;
    f>>m;

    //Graph gr(n);

    vector<Weigthed_Edge> edges;
    for(int i=0;i<m;++i)
    {
        f>>a>>b>>c;
        edges.push_back({a,b,c});
        //gr.add_edge(a,b);
        //gr.add_edge(b,a);
    }

    f.close();

    Graph::print_APM_Kruskal(g, edges, n);
    g.close();
    return 0;
}