#include <iostream>
#include <fstream>
#include <stdio.h>
#include <string.h>
#define MAXN 200000
using namespace std;
struct heap
{
    int x,y,cost;
}*Heap,*Sol;
struct nod
{
    int nr;
    nod *next;
}*First[MAXN+5];
int N,M,ACN,NS,Cost;
int Comp[MAXN+5],Visited[MAXN+5];
void Swap(int a,int b){
    heap aux=Heap[a];
    Heap[a]=Heap[b];
    Heap[b]=aux;
}
void Up(int k){
    if(k==1)
        return;
    int father=k/2;
    if(Heap[father].cost>Heap[k].cost)
    {
        Swap(father,k);
        Up(father);
    }
}
void InsertHeap(int i,int x,int y,int cost){
    Heap[i].x=x;
    Heap[i].y=y;
    Heap[i].cost=cost;
    Up(i);
}
void Read(){
    ifstream fin("apm.in");
    fin>>N>>M;
    Heap=new heap[M+5];
    Sol=new heap[N+5];
    int i,x,y,cost;
    for(i=1;i<=M;i++)
    {
        fin>>x>>y>>cost;
        InsertHeap(i,x,y,cost);
    }
    ACN=M;
    fin.close();
}
int ReturnMinSon(int father){
    int left=2*father,right=left+1;
    if(right>ACN)
        return left;
    if(Heap[left].cost<Heap[right].cost)
        return left;
    return right;
}
void Down(int father){
    if(2*father>ACN)
        return;
    int son=ReturnMinSon(father);
    if(Heap[son].cost<Heap[father].cost)
    {
        Swap(father,son);
        Down(son);
    }
}
void ReturnMin(int &x,int &y,int &cost){
    x=Heap[1].x;
    y=Heap[1].y;
    cost=Heap[1].cost;
    Heap[1].x=Heap[ACN].x;
    Heap[1].y=Heap[ACN].y;
    Heap[1].cost=Heap[ACN].cost;
    ACN--;
    Down(1);
}
void InsertInSol(int x,int y){
    NS++;
    Sol[NS].x=x;
    Sol[NS].y=y;
}
void Insert(int x,int y){
    nod *q=new nod;
    q->nr=y;
    q->next=First[x];
    First[x]=q;
}
void Update(int k,int nrcomp){
    Visited[k]=1;
    Comp[k]=nrcomp;
    nod *q;
    for(q=First[k];q;q=q->next)
    {
        if(Visited[q->nr]==0)
            Update(q->nr,nrcomp);
    }
}
void Add(int x,int y){
    if(Comp[x]==0&&Comp[y]==0)
    {
        Comp[0]++;
        Comp[x]=Comp[y]=Comp[0];
        Insert(x,y);
        Insert(y,x);
        InsertInSol(x,y);
        return;
    }
    if(Comp[x]==0)
    {
        int aux=x;
        x=y;
        y=aux;
    }
    memset(Visited,0,sizeof(Visited));
    Update(y,Comp[x]);
    Insert(x,y);
    Insert(y,x);
    InsertInSol(x,y);
}
void Resolve(){
    int i,x,y,cost;
    for(i=1;i<N&&ACN>0;i++)
    {
        ReturnMin(x,y,cost);
//        printf("%d %d %d  comp[x]=%d comp[y]=%d C=%d\n",cost,x,y,Comp[x],Comp[y],Cost);
        if(Comp[x]==Comp[y]&&Comp[x]!=0)
        {
            i--;
            continue;
        }
        Add(x,y);
        Cost+=cost;
    }
}
void Write()
{
    int i;
    ofstream fout("apm.out");
    fout<<Cost<<"\n";
    fout<<NS<<'\n';
    for(i=1;i<=NS;i++)
        fout<<Sol[i].x<<" "<<Sol[i].y<<"\n";
    fout.close();
}
int main()
{
    Read();
    Resolve();
    Write();
    return 0;
}