#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

typedef pair<int, pair<int,int>> piii;

vector<piii> E, Sol;

int N, M, x, y, c, k, cost, T[200010];
ifstream f("apm.in");
ofstream g("apm.out");

void load(){
    f >> N >> M;
    for( int i=1; i<=M; i++){
        f>>x>>y>>c;
        E.push_back({c,{x,y}});
    }
}

int reprezentant(int x){

    if(x==T[x]) return x;
    T[x] =  reprezentant(T[x]);
    return T[x];
}
void uneste(int i, int j){
    x = reprezentant(i);
    y = reprezentant(j);
    if(x == y) return;
    T[x] = reprezentant(y);
}

void kruskal ( ){

    sort(E.begin(), E.end());
    for(int i=1; i<=N; i++) T[i] = i;
    cost =0;
    for(auto i: E){
        x = i.second.first;
        y = i.second.second;
        if(reprezentant (x)!= reprezentant (y)){
            uneste(x, y);
            cost += i.first;
            Sol.push_back(i);
        }
    }
}

int main()
{
    load();
    kruskal();
    g<<cost<<'\n'<<Sol.size()<<'\n';
    for(auto i: Sol)
    g<<i.second.first<<" "<<i.second.second<<'\n';
    return 0;
}