#include <bits/stdc++.h>
#define DMAX 400002
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie
{
    int x,y,cost;
    friend bool operator>(muchie,muchie);
};
bool operator>(muchie a,muchie b)
{
    return a.cost>b.cost;
}
muchie muc[DMAX],rez[DMAX/2];
priority_queue<muchie,vector<muchie>,greater<muchie> > Heap;
int tata[DMAX],h[DMAX],n;
int Find(int x);
int costu,m,nrsel;
void Union(int x,int y);
int main()
{int i,rx,ry;
fin>>n>>m;
muchie a;
for(i=1;i<=m;i++)
    fin>>muc[i].x>>muc[i].y>>muc[i].cost,Heap.push(muc[i]);
nrsel=0;
while(nrsel<n-1)
{
    a=Heap.top();
    Heap.pop();
    rx=Find(a.x);
    ry=Find(a.y);
    if(rx!=ry)
        {nrsel++;rez[nrsel]=a;costu+=a.cost;Union(rx,ry);}
}
fout<<costu<<'\n';
fout<<nrsel<<'\n';
for(i=1;i<n;i++)
    fout<<rez[i].x<<' '<<rez[i].y<<'\n';



    return 0;
}
int Find(int x)
{int rad=x,aux;
    while(tata[rad])
        rad=tata[rad];
    while(tata[x])
    {
        aux=tata[x];
        tata[x]=rad;
        x=aux;
    }
    return rad;
}
void Union(int x,int y)
{
    x=Find(x);
    y=Find(y);

    if(h[x]>h[y])
        tata[y]=x;
    else
    {if(h[x]==h[y])
        h[y]++;
        tata[x]=y;
    }
}