//https://infoarena.ro/problema/APM

#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

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

int tata[200005], h[200005], cost=0;


struct muchie{
    int x, y, c;
}v[400005];
vector<muchie> sol;
bool cmp(muchie a, muchie b){
    return a.c < b.c;
}

int reprez(int a){
    while(tata[a]!=0)
        a=tata[a];
    return a;
}

void unire(muchie a){
    int repreza = reprez(a.x);
    int reprezb = reprez(a.y);
    if(h[repreza] > h[reprezb])
        tata[reprezb]=repreza;
    else
        tata[repreza]=reprezb;
    if(h[repreza] == h[reprezb])
        h[reprezb]++;
    cost += a.c;
    sol.push_back(a);
    
}

int main()
{
    int n, m;
    fin>>n>>m;
    for(int i=1; i<=m; i++)
        {
            int x, y, c;
            fin>>x>>y>>c;
            v[i].x=x;
            v[i].y=y;
            v[i].c=c;
        }
    sort(v+1, v+m+1, cmp);
    
    for(int i=1; i<=n; i++){
        tata[i]=0;
        h[i]=0;
    }
    int nr=0;
    for(int i=1; i<=m; i++)
    {
        muchie a = v[i];
        if(reprez(a.x) != reprez(a.y)){
            unire(a);
            nr++;
        }
        if(nr == n-1)
            break;
    }

    fout<<cost<<endl;
    fout<<n-1<<endl;
    for(muchie i : sol){
        fout<<i.x<<" "<<i.y<<endl;
    }
    return 0;
}