#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");
struct qer{int x,y,cost;}v[400001],sol[400001];
bool comp(const qer &a, const qer &b){return a.cost<b.cost;}
int n,m,a,b,c,i,tata[200001],sz[200001],rsp,nr;
int find_parent(int nod){
    if(tata[nod]==nod)return nod;
    return tata[nod]=find_parent(tata[nod]);
}
void unite(int a,int b){
    a=find_parent(a);
    b=find_parent(b);
    if(sz[a]>sz[b])swap(a,b);
    tata[a]=b;
    sz[b]+=sz[a];
}
int main()
{
    fin>>n>>m;for(i=1;i<=n;i++)tata[i]=i,sz[i]=1;
    for(i=1;i<=m;i++){
        fin>>a>>b>>c;
        v[i]={a,b,c};
    }sort(v+1,v+m+1,comp);
    for(i=1;i<=m;i++){
        a=v[i].x;
        b=v[i].y;
        c=v[i].cost;
        if(find_parent(a)!=find_parent(b)){
         unite(a,b);
         rsp+=c;
         sol[++nr]={a,b,c};
        }
    }
    fout<<rsp<<'\n'<<n-1<<'\n';
    for(i=1;i<=nr;i++)fout<<sol[i].x<<' '<<sol[i].y<<'\n';
}