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