#include <fstream>
#include <algorithm>
#include <vector>
#include <map>
#include <cstring>
using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

struct muchie{
    int x, y, c;
}v[10005];

bool cmp(muchie A, muchie B){
    return A.c<B.c;
}

int n, m;

struct DSU{
    int rep[200005], sz[200005];
    DSU(int n){
        for(int i=1;i<=n;i++){
            rep[i]=i;
            sz[i]=1;
        }
    }
    int get_rep(int a){
        if(a==rep[a])return a;
        return rep[a]=get_rep(rep[a]);
    }
    void join(int a, int b){
        int ta=get_rep(a);
        int tb=get_rep(b);
        if(sz[ta]>sz[tb]){
            swap(ta, tb);
        }
        rep[ta]=tb;
        sz[tb]+=sz[ta];
    }
    bool find(int a, int b){
        int ta=get_rep(a);
        int tb=get_rep(b);
        return ta==tb;
    }
};

void kruskal(){
    DSU dsu(n);
    sort(v+1, v+m+1, cmp);
    int cost=0;
    vector<pair<int,int>> sol;
    for(int i=1;i<=m;i++){
        if(!dsu.find(v[i].x, v[i].y)){
            dsu.join(v[i].x, v[i].y);
            cost+=v[i].c;
            sol.emplace_back(v[i].x, v[i].y);
        }
    }
    cout<<cost<<'\n'<<n-1<<'\n';
    for(auto it:sol){
        cout<<it.first<<" "<<it.second<<'\n';
    }
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x, y, c;
        cin>>x>>y>>c;
        v[i]={x, y, c};
    }
    kruskal();
}