#include <fstream>
#include <queue>
#include <algorithm>
#define x first
#define y second
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
struct cel{int a,b,c;} v[400010];
queue< pair<int,int> > muchie;
pair<int,int> jeg;
int n,m,frec[200010],i,nr;
long long sum;

int tata(int a)
{
    while(a != frec[a])
        a = frec[a];
    return a;
}
bool cmp(cel x,cel y)
{
    return x.c<y.c;
}
int main()
{
    cin>>n>>m;
    for(i=1;i<=n;++i)
        frec[i]=i;
    for(i=1;i<=m;++i)
        cin>>v[i].a>>v[i].b>>v[i].c;
    sort(v+1,v+1+m,cmp);
    for(i=1;i<=m;++i){
        int k1 = tata(v[i].a);
        int k2 = tata(v[i].b);
        if(k1 != k2){
            if(k1 < k2)
                frec[k1] = k2;
            else
                frec[k2] = k1;
            ++nr;
            jeg=make_pair(v[i].a,v[i].b);
            muchie.push(jeg);
            sum += v[i].c;
        }
    }

    cout<<sum<<'\n'<<nr<<'\n';
    while(!muchie.empty()){
        jeg=muchie.front();
        cout<<jeg.y<<" "<<jeg.x<<'\n';
        muchie.pop();
    }
    return 0;
}