#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

int t[20005], h[20005], n, m, cnt;
struct muchie{
    int x, y, c;
}v[40005];

vector<muchie> final;

bool cmp(const muchie &a, const muchie &b) {
    return a.c < b.c;
}

void init(int a)
{
    t[a] = a;
    h[a] = 0;
}

int find(int a){
    if(t[a] == a)
        return a;
    t[a] = find(t[a]);
    return t[a];
}

void reun(muchie a){
    int ra = find(a.x);
    int rb = find(a.y);
    if(h[ra] > h[rb])
        t[rb] = ra;
        else{
            t[ra] = rb;
            if(h[ra] == h[rb])
                h[rb] += 1;}
    cnt += a.c;
    final.push_back(a);
}



int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++){
        int a, b, c;
        fin>>a>>b>>c;
        v[i].x=a;
        v[i].y=b;
        v[i].c=c;
    }

    sort(v + 1, v + m + 1, cmp);

    for(int i=1; i<=n; i++)
            init(i);
    int nr=0;
    for(int i=1; i<=m; i++)
    {
        if(find(v[i].x) != find(v[i].y)){
            reun(v[i]);
            nr++;
            if(nr==n-1)
                break;    
        }
    }
    fout<<cnt<<'\n'<<final.size()<<'\n';
    for (size_t i = 0; i < final.size(); i++) {
        fout << final[i].x << " " << final[i].y << '\n';
    }
    return 0;
}