#include <bits/stdc++.h>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct Edge{
    int x,y;
    Edge(){}
    Edge(int x,int y){this->x = x;this->y = y;}
};

vector<int> h;
vector<int> t;
vector<int> nr;
vector<vector<int>> grph;
vector<vector<Edge>> cmp;
int cost = 0;
int nrcmp= -1;
void init(int n){
    h = vector<int>(n+1,0);
    t = vector<int>(n+1,-1);
    nr = vector<int>(n+1,1);
    cmp = vector<vector<Edge>>(n+1);
}

int get_root(int k){
    if(t[k]==-1){
        return k;
    }

    return (t[k] = get_root(t[k]));
}

void uni(int x,int y,int z){
    int rtx = get_root(x);
    int rty = get_root(y);
    if(rtx == rty)
        return;
    if(h[rtx]>h[rty]){
        t[rty] = get_root(x);
        nr[rtx] += nr[rty];

        cmp[rtx].emplace_back(Edge(x,y));
        cost+=z;
        nrcmp = max(nrcmp,nr[rtx]);
    } else{
        if(h[rtx] == h[rty])
            ++h[rty];
        t[rtx] = get_root(y);
        nr[rty] += nr[rtx];
        cmp[rty].emplace_back(Edge(x,y));
        cost+=z;
        nrcmp = max(nrcmp,nr[rty]);
    }

}


int main(){
    int n,m;
    fin>>n>>m;
    init(n);
    for(int i=0;i<m;i++){
        int x,y,z;
        fin>>x>>y>>z;
        grph.push_back({x,y,z});
    }

    sort(grph.begin(),grph.end(),[](vector<int> a, vector<int>b){return a[2]<b[2];});
    for (const auto &item: grph) {
        uni(item[0],item[1],item[2]);
    }

    int indx = 0;
    int val = 0;
    int cnt = 0;
    for (const auto &item: nr) {
        if(val<item){
            val = item;
            indx = cnt;
        }
        cnt++;
    }
    fout<<cost<<endl;
    fout<<--nrcmp<<endl;

    for (const auto &item: cmp) {
        for (const auto &item1: item) {
            fout<<item1.x<<" "<<item1.y<<endl;
        }
    }
    return 0;
}