#include <bits/stdc++.h>

using namespace std;

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

int tata[100005],h[100005];
struct Muchie{
    int x,y,c;
};

int Find(int a){
    int x = a;
    while (tata[x]!=x){
        x = tata[x];
    }
    int y = a;
    while (tata[y]!=y){
        int cp = tata[y];
        tata[y] = x;
        y = cp;
    }
    return x;
}

void Unite(int a,int b){
    int x = Find(a);
    int y = Find(b);
    if (h[x]==h[y]){
        h[x]++;
        tata[y] = x;
        return;
    }
    if (h[x]>h[y]) tata[y] = x;
    else if (h[x]<h[y]) tata[x] = y;
}

bool Comp(Muchie a,Muchie b){
    return a.c<b.c;
}

int main()
{
    int n,m;
    fin >> n >> m;
    for (int i=1;i<=n;++i){
        tata[i] = i;
        h[i] = 1;
    }
    vector <Muchie> gr;
    for (int i=1;i<=m;++i){
        int x,y,c;
        Muchie loc;
        fin >> x >> y >> c;
        loc.x = x;
        loc.y = y;
        loc.c = c;
        gr.push_back(loc);
    }
    sort(gr.begin(),gr.end(),Comp);
    int cst = 0;
    vector <Muchie> ans;
    for (auto edge:gr){
        int x = edge.x;
        int y = edge.y;
        int c = edge.c;
        if (Find(x)!=Find(y)){
            cst += c;
            ans.push_back(edge);
            Unite(x,y);
        }
    }
    fout << cst << '\n';
    fout << ans.size() << '\n';
    for (auto loc:ans){
        fout << loc.x << ' ' << loc.y << '\n';
    }
    return 0;
}