//#include <iostream>
#include <fstream>
#include <deque>
#include <vector>
#include <unordered_set>
#include <algorithm>

using namespace std;

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

unordered_set <int> um;
int tata[200005],sz[200005],n,m;
long long cost;
vector<int> graf[200005],legit[200005];
vector<pair<int,int> > v[200005];
pair<int,pair<int,int> > edge[800005];

int daddy(int a){
    if(tata[a]==a){
        return a;
    }
    tata[a]=daddy(tata[a]);
    return tata[a];
}
void unite(int a,int b,int c){
    if(daddy(a)!=daddy(b)){
        if(sz[tata[a]]>sz[tata[b]]){
            tata[b]=tata[a];
            sz[tata[a]]+=sz[tata[b]];
        }
        else{
            tata[a]=tata[b];
            sz[tata[b]]+=sz[tata[a]];
        }
        cost+=c;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
}
int main()
{
    int t,a,b,c;
        cin>>n>>m;
        cost=0;
        um.clear();
        for(int i=1;i<=n;i++){
            tata[i]=i;
            sz[i]=1;
        }
        for(int i=1;i<=m;i++){
            cin>>a>>b>>c;
            v[a].push_back(make_pair(b,c));
            v[b].push_back(make_pair(a,c));
            edge[i*2-1]=make_pair(c,make_pair(a,b));
            edge[i*2]=make_pair(c,make_pair(b,a));
        }
        sort(edge+1,edge+2*m+1);
        for(int i=1;i<=m;i++){
            unite(edge[i].second.first,edge[i].second.second,edge[i].first);
        }
        cout<<cost<<"\n"<<n-1<<"\n";
        for(int i=1;i<=n;i++){
            for(auto u:graf[i]){
                if(i>u){
                    cout<<i<<" "<<u<<"\n";
                }
            }
        }
    return 0;
}