#include <fstream>
#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,x,y,cer;
struct ceva
{
    int x1,x2,pow;
}v[250001];
struct ceva2
{
    int m1,m2;
}rez[250001];
int t[100001];
int fnd(int x)
{
    int y,aux;
    y=x;
    while(y!=t[y])
    {
        y=t[y];
    }
    while(x!=t[x])
    {
        aux=t[x];
        t[x]=y;
        x=aux;
    }
    return y;
}
bool comp(ceva x,ceva y)
{
    if(x.pow!=y.pow)
    return x.pow<y.pow;
        return x.pow>y.pow;
}
void unite(int x,int y)
{
    int tx=fnd(x);
    int ty=fnd(y);
    t[ty]=tx;
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
        t[i]=i;
    for(int i=1;i<=m;i++)
    {
        fin>>v[i].x1>>v[i].x2>>v[i].pow;
    }
    sort(v+1,v+m+1,comp);
    int cnt=0;
    long long sum=0;
    for(int i=1;i<=m;i++)
    {
        if(fnd(v[i].x1)!=fnd(v[i].x2))
            unite(v[i].x1,v[i].x2),cnt++,sum+=v[i].pow,rez[cnt].m1=v[i].x1,rez[cnt].m2=v[i].x2;
        if(cnt==n-1)
        {
            fout<<sum<<'\n'<<cnt<<'\n';
            for(int j=1;j<=cnt;j++)
                fout<<rez[j].m2<<" "<<rez[j].m1<<'\n';
            return 0;
        }
    }
    return 0;
}