#include <fstream>
#include <algorithm>

#define MaxN 200001
#define MaxM 400001
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int n,m, tata[MaxN],k, A[MaxM], B[MaxM];
int cost;
struct muchie
{
    int a,b,cost;
};
muchie M[MaxM];
bool criteriu(muchie A, muchie B) {return A.cost<B.cost;}

int tatuca(int x)
{
    if(tata[x]!=x) tata[x]=tatuca(tata[x]);
    return tata[x];
}
void apm()
{
    int i, ta, tb;
    for(i=1;i<=n;i++)
        tata[i]=i;
    for(i=1;i<=m;i++)
    {
        ta=tatuca(M[i].a);
        tb=tatuca(M[i].b);
        if(ta!=tb)
        {
            cost=cost+M[i].cost;
            k++;
            A[k]=M[i].a;
            B[k]=M[i].b;
            tata[ta]=tb;
        }
    }
}
int main()
{
    int a,b,c,i,j;

    in>>n>>m;
    for(i=1;i<=m;i++)
    {
        in>>a>>b>>c;
        M[i].a=a;
        M[i].b=b;
        M[i].cost=c;
    }
    sort(M+1,M+m+1,criteriu);
    apm();
    out<<cost<<"\n";
    out<<n-1<<"\n";
    for(i=1;i<=k;i++)
        out<<B[i]<<" "<<A[i]<<"\n";
    out.close();
    in.close();
    return 0;
}