#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");
int n,i,j,x,y,z,repr[1000105],n1,n2,ales,m,val1,val2;
long long costmin;
int depus;
struct haha
{
    int x; int y; int cost;
} v[1000105];
struct hh
{
    int a; int b;
} afis[1000105];
int crit(haha u, haha v)
{
    if(u.cost>v.cost) return 0;
    return 1;
}
int f(int nod)
{
    if(repr[nod]==nod) return nod;
    else return f(repr[nod]);
}
void u(int a, int b)
{
    repr[a]=b;
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++) fin>>v[i].x>>v[i].y>>v[i].cost;
    for(i=1;i<=n;i++) repr[i]=i;
    sort(v+1,v+1+m,crit);
    for(i=1;i<=m and ales<n-1;i++)
    {
        n1=v[i].x;
        n2=v[i].y;
        val1=f(n1);
        val2=f(n2);
        if(val1!=val2)
        {
            depus++;
            afis[depus].a=n1;
            afis[depus].b=n2;
            costmin+=v[i].cost;
            ales++;
            u(val1,val2);
        }
    }
    fout<<costmin<<'\n';
    fout<<n-1<<'\n';
    for(i=1;i<=depus;i++) fout<<afis[i].a<<' '<<afis[i].b<<'\n';
    return 0;
}