#include <cstdio>
#define nmax 200010
#include <queue>
#include <vector>
using namespace std;

int n,m,s;
int gr[nmax];
priority_queue <pair<int,pair<int,int> > > heap;
vector <pair<int,int> > rs;

int grupa(int);
void read();
void kruskal();
void print();

int main(){
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    read();
    kruskal();
    print();
    return 0;
}
void read(){
    scanf("%d %d ",&n,&m);
    int x,y,z;
    for(int i = 1;i <= m;i++){
        scanf("%d %d %d ",&x,&y,&z);
        heap.push(make_pair(-z,make_pair(x,y)));
    }
}
int grupa(int i){
    if(gr[i] == i)return i;
    gr[i] = grupa(gr[i]);
    return gr[i];
}
void kruskal(){
    for(int i = 1;i <= n;i++)gr[i] = i;
    int x,y,z;
    while(rs.size() < n-1){
        x = heap.top().second.first;
        y = heap.top().second.second;
        z = -heap.top().first;
        heap.pop();
        if(grupa(x) != grupa(y)){
            s += z;
            gr[grupa(x)] = grupa(y);
            rs.push_back(make_pair(x,y));
        }
    }
}
void print(){
    printf("%d\n",s);
    printf("%d\n",n-1);
    for(vector <pair<int,int> > :: iterator it = rs.begin();it != rs.end();++it)printf("%d %d\n",it->first,it->second);
}