#include <bits/stdc++.h>
#define oo 5555555

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");


struct Muchie
{
    int x,y,c,ok;
    bool operator < (const Muchie A) const
    {
        return A.c>c;
    }
};

Muchie A[400005];
int n,m;
int t[200005];

int Find(int x)
{
    int y,rad=x;
    while(t[rad]!=0)
        {
            rad=t[rad];
        }
    while(t[x]!=0)
    {
        y=t[x];
        t[x]=rad;
        x=y;
    }
    return rad;
}

void Union(int x,int y)
{
    t[y]=x;
}

void Kruskal()
{
    int s=0,cnt=0;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        x=Find(A[i].x);
        y=Find(A[i].y);
        if(x!=y)
        {
            s+=A[i].c;
            cnt++;
            A[i].ok=1;
            Union(x,y);
        }
    }
    fout<<s<<"\n"<<cnt<<"\n";
    for(int i=1;i<=m;i++)
        if(A[i].ok==1) fout<<A[i].x<<" "<<A[i].y<<"\n";
}

int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
        {
            int x,y,c;
            fin>>A[i].x>>A[i].y>>A[i].c;
        }
    sort(A+1,A+m+1);
    Kruskal();
    return 0;
}