#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
#pragma pack(1)
#define MAXIM 200001
int *t=new int[MAXIM](), *rg=new int[MAXIM]();

struct muchie
{
    int a, b, c;
}*mu=new muchie[400001](), *sol=new muchie[MAXIM];

bool cmp(muchie a, muchie b)
{
    return a.c<b.c;
}

int findn(int nod)
{
    int R=nod, temp;
    while(t[R])
    {
        R=t[R];
    }
    while(t[nod])
    {
        temp=t[nod];
        t[nod]=R;
        nod=temp;
    }
    return R;
}

void unite(int x, int y)
{
    if(rg[x]<rg[y]) t[x]=y;
    else t[y]=x;
    if(rg[x]==rg[y]) rg[x]++;
}

int main()
{
    int n,m, sum=0, j=0;
    in>>n>>m;
    for(int i=0;i<m;i++) in>>mu[i].a>>mu[i].b>>mu[i].c;
    sort(mu,mu+m,cmp);
    for(int i=1;i<=n;i++) rg[i]=1;
    for(int i=0;i<m;i++)
    {
        int n1=mu[i].a,n2=mu[i].b;
        if((findn(n1)==0&&findn(n2)==0)||findn(n1)!=findn(n2))
        {
            sum=sum+mu[i].c;
            unite(findn(n1),findn(n2));
            sol[j].a=mu[i].a;
            sol[j].b=mu[i].b;
            j++;
        }
    }
    out<<sum<<'\n'<<j<<'\n';
    for(int i=0;i<j;i++) out<<sol[i].b<<' '<<sol[i].a<<'\n';
    return 0;
}