#include <bits/stdc++.h>
#define ll unsigned long long

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m;
struct muchie{
    int x;
    int y;
    int cost;
}v[200001];
bool cmp(muchie a, muchie b){
    return a.cost<b.cost;
}
int tata[100001];
int root(int x){
    while(tata[x]>0)
        x = tata[x];
    return x;
}
void unite(int x, int y){
    if(-tata[x] < - tata[y]){ // vreau ca x sa fie ala mai mare
        swap(x,y);
    }
    tata[x]+=tata[y];
    tata[y]=x;
}
int main(){
    fin>>n>>m;
    for(int i = 1; i<=m; i++){
        fin>>v[i].x>>v[i].y>>v[i].cost;
    }
    for(int i = 1; i<=n; i++)
        tata[i] = -1;
    sort(v+1,v+m+1,cmp);
    int cnt = 0,suma = 0;
    pair<int,int>lista[100001];
    for(int i = 1; i<=m && cnt < n - 1; i++){
       int x = v[i].x;
       int y = v[i].y;
       int rootx = root(x);
       int rooty = root(y);
       if(rootx != rooty){
        unite(rootx, rooty);
        suma+=v[i].cost;
        cnt++;
        lista[cnt].first = x;
        lista[cnt].second = y;
       }
    }
    fout<<suma<<'\n';
    fout<<cnt<<'\n';
    for(int i = 1; i<=cnt ; i++)
        fout<<lista[i].first<<" "<<lista[i].second<<'\n';
   return 0;
}