#include <bits/stdc++.h>
using namespace std;
const int nm=2e5+5;
int p[nm],h[nm];

struct mlcb{
    int x,y,c;
};
vector<mlcb>v;

bool cmp(mlcb a, mlcb b){
    return a.c<b.c;

}
int Find(int x){
    while(x!=p[x]){
        x=p[x];
    }
    return x;
}
void Union(int x, int y){
    x=Find(x);
    y=Find(y);
    if(h[x]<h[y])swap(x,y);
    p[y]=x;
    h[x]+=h[y];
    h[y]=0;

}
int main()
{
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        p[i]=i;
    }
    for(int i=1;i<=m;i++){
        int c,a,b;
        cin >> a >> b >> c;
        v.push_back({a,b,c});
    }
    sort(v.begin(),v.end(),cmp);
    vector<pair<int,int>>rez;
    int sum=0;
    for(int i=0;i<v.size();i++){
        if(Find(v[i].x)!=Find(v[i].y)){
            Union(v[i].x,v[i].y);
            sum+=v[i].c;
            rez.push_back({v[i].x,v[i].y});
        }
    }
    cout << sum << '\n' << n-1 << '\n';
    for(int i=0;i<rez.size();i++){
        cout << rez[i].first << ' ' << rez[i].second << '\n';
    }
    return 0;
}