#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#define m1 g[i].second.first
#define m2 g[i].second.second
#define cost g[i].first
#define nmax 200005
using namespace std;
vector <pair<int,pair<int,int> > >g;
vector <pair<int,int> >apm;
FILE *f1=fopen("apm.in","r"),*f2=fopen("apm.out","w");
int n,m,cst;
bool use[nmax];
int tt[nmax],rg[nmax];
void citire()
{
    int i,x,y,c;
    fscanf(f1,"%d %d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(f1,"%d %d %d",&x,&y,&c);
        g.push_back(make_pair(c,make_pair(x,y)));
    }
    for(i=1;i<=n;i++)
    {tt[i]=i;rg[i]=i;}
}
int tata(int x)
{
    int r=x,aux;
    while(tt[r]!=r)r=tt[r];
    while(x!=tt[x])
    {
        aux=tt[x];
        tt[x]=r;
        x=aux;
    }
    return r;
}
void unite(int x,int y)
{
    if(rg[x]>rg[y]){tt[y]=x;rg[x]++;}
    else tt[y]=x;
}
void genApm()
{
    int i;
    sort(g.begin(),g.end());
    for(i=0;i<g.size();i++)
    {
        int x=tata(m1);
        int y=tata(m2);
        if(x!=y)
        {
            unite(x,y);
            cst+=cost;
            apm.push_back(make_pair(m1,m2));
        }
    }
}
int main()
{
    citire();
    genApm();
    fprintf(f2,"%d\n%d\n",cst,apm.size());
    int i;
    for(i=0;i<apm.size();i++)
    fprintf(f2,"%d %d\n",apm[i].first,apm[i].second);
    return 0;
}