#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define MAX 400100
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct edge
{
        int x,y,cost;
};

int parent[MAX];
int height[MAX];
vector <edge> graph;
vector <edge> apcm;
int cmp(edge a,edge b)
{
        return a.cost<b.cost;
}
void read_graph(int &no_nodes,int &no_edges)
{
        int i;
        fin>>no_nodes>>no_edges;
        edge e;
        for(i=1; i<=no_edges; i++)
        {
                fin>>e.x>>e.y>>e.cost;
                graph.push_back(e);
        }
}
int find_parent(int i)
{
        if(parent[i]==i)
                return i;
        return find_parent(parent[i]);
}

void union_trees(int root1,int root2)
{
        if(height[root1]>height[root2])
                parent[root2]=root1;
        else if(height[root1]==height[root2])
        {
                parent[root2]=root1;
                height[root1]++;
        }
        else
        {
                parent[root1]=root2;
        }
}
void kruskal(int no_nodes,int no_edges)
{
        int i;
        int min_cost=0,nr_edges=0;
        int node1,node2,root1,root2;
        sort(graph.begin(),graph.end(),cmp);
        for(i=1; i<=no_nodes; i++)
                parent[i]=i;
        i=0;
        while(nr_edges<no_nodes-1)
        {
                node1=graph[i].x;
                node2=graph[i].y;
                root1=find_parent(node1);
                root2=find_parent(node2);
                if(root1!=root2)
                {
                        nr_edges++;
                        min_cost+=graph[i].cost;
                        union_trees(root1,root2);
                        apcm.push_back(graph[i]);
                }
                i++;
        }
        fout<<min_cost<<endl<<nr_edges<<endl;
        for(i=0; i<nr_edges; i++)
                fout<<apcm[i].x<<" "<<apcm[i].y<<endl;
}
int main()
{
        int no_nodes,no_edges;
        read_graph(no_nodes,no_edges);
        kruskal(no_nodes,no_edges);
        return 0;
}