#include <fstream>
#include <math.h>
#include <algorithm>
#include <vector>
#define NMAX 400000 + 1

using namespace std;

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




struct edge
{
    int node1,node2;
    int cost;
};

inline int mycomp(edge a,edge b)
{
    return a.cost < b.cost;
}

vector<edge> edge_vector;
vector<edge> min_span;

int father[NMAX];
int height[NMAX];


void read_data(int &n,int &m)
{
    int i;
    edge temp;

    in>>n>>m;

    for(i = 0 ; i < m ; ++i)
    {
        in>>temp.node1>>temp.node2>>temp.cost;
        edge_vector.push_back(temp);

    }

}

int find_father(int node)
{
    while( father[node] != node)
        node = father[node];

    return node;

}

int Union(int node1,int node2)
{
    if(height[node1] > height[node2])
    {
        father[node2] = node1;
    }
    else  if( height[node1] == height[node2])
    {

        ++height[node1];
        father[node2]=node1;
    }
    else
        father[node1]=node2;

}

void kruskal(int n,int m)
{

    int accepted_edges  = 0;
    int current_edge = 0;
    int cost_minim = 0;

    sort(edge_vector.begin(),edge_vector.end(),mycomp);


    int i;

    int node1,node2,fn1,fn2;


    for( i = 1 ; i<=n; ++i)
        father[i]=i;

    while (accepted_edges < n-1)
    {
        node1 = edge_vector[current_edge].node1;
        node2 = edge_vector[current_edge].node2;
        fn1   = find_father(node1);
        fn2   = find_father(node2);

        if(node1 == 3 && node2 == 7)
            int temp = 2;


        if(fn1 != fn2 )
        {
            cost_minim += edge_vector[current_edge].cost;
            Union(fn1,fn2);
            ++accepted_edges;
            min_span.push_back(edge_vector[current_edge]);

        }

        ++current_edge;
    }

    out<<cost_minim<<'\n'<<min_span.size()<<'\n';

    for(i = 0 ; i < min_span.size() ; ++i)
        out<<min_span[i].node1 << ' '<<min_span[i].node2<<'\n';

}

int main()
{
    int n,m;
    int i;


    read_data(n,m);
    kruskal(n,m);






    return 0;

}