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

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

int n, m, a, b, c, ans;
int i, j;
int tata[DIM], costt[DIM];
struct elem{
    int x, y, cost;
};
vector <elem> G;
vector <pair <int, int> > ans_m;

bool comp(elem a, elem b){
    return a.cost<b.cost;
}

int get_root(int nod){
    while(tata[nod]>0)
        nod=tata[nod];
    return nod;
}

void join(int nod1, int nod2, int c){
    int root1=get_root(nod1);
    int root2=get_root(nod2);
    if(tata[root1]<=tata[root2]){
        tata[root1]+=tata[root2];
        tata[root2]=root1;
        costt[root1]+=costt[root2]+c;
        ans=max(ans, costt[root1]);
    }else{
        tata[root2]+=tata[root1];
        tata[root1]=root2;
        costt[root2]+=costt[root1]+c;
        ans=max(ans, costt[root2]);
    }
}

int main(){
    fin>>n>>m;
    for(i=1; i<=m; i++){
        fin>>a>>b>>c;
        G.push_back({a, b, c});
        G.push_back({b, a, c});
    }
    for(i=1; i<=n; i++)
        tata[i]=-1;
    sort(G.begin(), G.end(), comp);
    for(auto k:G){
        if(get_root(k.x)!=get_root(k.y)){
            join(k.x, k.y, k.cost);
            ans_m.push_back(make_pair(k.x, k.y));
        }
    }
    fout<<ans<<"\n"<<ans_m.size()<<"\n";
    for(auto k:ans_m)
        fout<<k.first<<" "<<k.second<<"\n";
}