#include <fstream>
#include<algorithm>
using namespace std;
ifstream cin ("apm.in");
ofstream cout ("apm.out");
int n,m,tata[200001],rang[200001],k,o,cost=0;
struct bla
{
    int x,y,c;
} v[400001],muchii[400001];
bool sortare (bla x1,bla y1)
{
    return x1.c<y1.c;
}
void citire ()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>v[i].x>>v[i].y>>v[i].c;
        sort(v+1,v+1+m,sortare);
}
void init ()
{
    for(int i=1;i<=n;i++)
        tata[i]=i;
}
int cauta (int nod)
{
    if(tata[nod]!=nod)
        tata[nod]=cauta(tata[nod]);
    return tata[nod];
}
void uneste (int p1,int p2 )
{ muchii[++k]=v[o]; cost+=v[o].c;
    if(rang[p1]>rang[p2])
        tata[p2]=p1;
    else tata[p1]=p2;
    if(rang[p1]==rang[p2]) rang[p1]++;
}
void parcurg ()
{
    for(int i=1;i<=m;i++)
    { o=i;
        int p1=cauta(v[i].x);
        int p2=cauta(v[i].y);
        if(p1!=p2)
            uneste(p1,p2);
    }
}
void scrie ()
{ cout<<cost<<"\n"<<k<<"\n";
    for(int i=1;i<=k;i++)
        cout<<muchii[i].x<<" "<<muchii[i].y<<"\n";
}
int main()
{
    citire();
    init();
    parcurg();
    scrie();
    return 0;
}