// Algoritmul lui Krushal
#include <bits/stdc++.h>
#define Dim 400006
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int N,M,cnt,maxim,minim;
long cost1;
int c[Dim];

struct graf
{
    int cs,cd,cost;
}Mch[Dim],MR[Dim];

void Citire()
{
    f>>N>>M;
    for(int i=1;i<=M;i++)
       f>>Mch[i].cs>>Mch[i].cd>>Mch[i].cost;
    for(int i=1;i<=N;i++) c[i]=i;
}

bool tester(graf &x,graf &y)
{
    if(x.cost<=y.cost)
    {
        switch(x.cs,y.cs);
        switch(x.cd,y.cd);
        return 1;
    }
    else return 0;
}

int main()
{
    Citire();
    sort(Mch+1,Mch+M+1,tester);
    for(int i=1;i<=M;i++)
    if(c[Mch[i].cs]!=c[Mch[i].cd])
    {
        MR[++cnt].cs=Mch[i].cs;
        MR[cnt].cd=Mch[i].cd;
        cost1+=Mch[i].cost;
        maxim=max(c[Mch[i].cs],c[Mch[i].cd]);
        minim=min(c[Mch[i].cs],c[Mch[i].cd]);
        for(int j=1;j<=N;j++)
            if(c[j]==maxim) c[j]=minim;

    }
    g<<cost1<<'\n'<<N-1<<'\n';
    for(int i=1;i<=N-1;i++)
        g<<MR[i].cs<<" "<<MR[i].cd<<'\n';
    return 0;
}