#include <bits/stdc++.h>
#define Nmax 200005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie
{
    int x,y,cost,setat;
};
inline bool cmp(const muchie A,const muchie B)
{
    return A.cost<B.cost;
}
muchie v[Nmax];
int t[Nmax],n,m;
void Citire()
{
    int i;
    fin>>n>>m;
    for(i=1;i<=m;i++)
        fin>>v[i].x>>v[i].y>>v[i].cost;
    fin.close();
    sort(v+1,v+m+1,cmp);
}
inline int Find(int k)
{
    int rad,z;
    rad=k;
    while(t[rad]!=0) rad=t[rad];
    while(k!=rad)
    {
        z=k;
        k=t[k];
        t[z]=rad;
    }
    return rad;
}
inline void Union(int x,int y)
{
    t[x]=y;
}
void Rezolvare()
{
    int i,costtot=0,cnt=0,x,y;
    for(i=1;i<=m;i++)
    {
        x=Find(v[i].x);
        y=Find(v[i].y);
        if(x!=y)
        {
            costtot+=v[i].cost;
            v[i].setat=1;
            cnt++;
            Union(x,y);
        }
    }
    fout<<costtot<<"\n"<<cnt<<"\n";
    for(i=1;i<=m;i++) if(v[i].setat==1)
        fout<<v[i].x<<" "<<v[i].y<<"\n";
    fout.close();
}
int main()
{
    Citire();
    Rezolvare();
    return 0;
}