#include <fstream>
#include <algorithm>
#include <iostream>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m;
typedef struct o{int x;int y;int C;}O;
int P[200200];
int R[200200];
O A[400200];
bool cmp(O a,O b)
{
    return a.C<b.C;
}
int check_p(int x)
{
    if (P[x]!=x)
        P[x]=check_p(P[x]);
    return P[x];
}
void merge_s(int x,int y)
{
    x=check_p(x);
    y=check_p(y);
    if (R[x]>R[y])
        P[y]=x;
    else
        P[x]=y;
    if (R[x]==R[y])
        R[y]++;
}
int main()
{
    fin>>n>>m;
    for (int i=1;i<=n;i++)
        P[i]=i,R[i]=0;
    for (int i=1;i<=m;i++)
        fin>>A[i].x>>A[i].y>>A[i].C;
    sort(A+1,A+m+1,cmp);
    int k=0,s=0;
    int B[400400];
    for (int i=1;i<=m;i++)
    {
        if (check_p(A[i].x)!=check_p(A[i].y))
        {
            merge_s(A[i].x,A[i].y);
            s+=A[i].C;
            B[++k]=i;
        }
    }
    fout<<s<<"\n"<<k<<"\n";
    for (int i=1;i<=k;i++)
        fout<<A[B[i]].x<<' '<<A[B[i]].y<<"\n";
    return 0;
}