#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define X vecini[node][j]
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchii{
    int x,y,c;
}m[400005],rez[200005];
int n,M,sum,root,tati[200005];
int arb[200005],node,k;
vector<int>vecini[200005];

bool comp(muchii a,muchii b)
{
    return(a.c<b.c);
}

void join(int i)
{
    root=tati[m[i].x]; node=tati[m[i].y];
    if(arb[node]>arb[root]) swap(node,root);
    for(int j=0;j<vecini[node].size();++j)
    {
        tati[X]=root;
        vecini[X].resize(0);
        vecini[X].push_back(root);
        vecini[root].push_back(X);
    }
    tati[node]=root;
    vecini[node].resize(0);
    vecini[node].push_back(root);
    vecini[root].push_back(node);
    arb[root]+=arb[node]; arb[node]=0;
    ++k;
    rez[k].x=root; rez[k].y=node;
    sum+=m[i].c;
}

int main()
{
    f>>n>>M;
    for(int i=1;i<=M;++i)
    {
        f>>m[i].x>>m[i].y>>m[i].c;
    }
    sort(m+1,m+M+1,comp);
    for(int i=1;i<=n;++i) tati[i]=i, arb[i]=1;
    for(int i=1;i<=M;++i)
    {
        if(tati[m[i].x]!=tati[m[i].y]) join(i);
    }
    g<<sum<<'\n'<<k<<'\n';
    for(int i=1;i<=k;++i)
    {
        g<<rez[i].x<<' '<<rez[i].y<<'\n';
    }
    return 0;
}