#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;
    parent[i]=find_parent(parent[i]);
    return parent[i];
}

void union_trees(int root1,int root2)
{
    if(height[root1]>height[root2])
        parent[root2]=root1;
    else
        if(height[root1]<height[root2])
        parent[root1]=root2;
    else
      {

       height[root1]++;
       parent[root2]=root1;
      }
}

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;
    for(i=0;i<no_edges;i++)
    {
         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]);
        }

    }
    fout<<min_cost<<endl<<nr_edges<<endl;
    for(i=0;i<apcm.size();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;
}