#include <fstream>
#include <algorithm>
#define NMAX 200005
#define MMAX 400005
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n, m;
int T[NMAX];


struct muchii{
    int x, y, cost;
    bool operator<(const muchii &other) const {
        if(cost == other.cost)
        {
            if(x == other.x)
                return y<other.y;
            return x<other.x;
        }
        return cost<other.cost;
    }
}M[MMAX], sol[NMAX];

void init(){
    for(int i=1; i<=n; i++)
        T[i] = i;
}

int opParc(int x){
    if(T[x] == x)
    {

        return x;
    }
    int ajut = opParc(T[x]);
    T[x]=ajut;
    return ajut;

}
int sum=0;
void solve(){
    int nrmuchii = 0;
    for(int i=1; i<=m && nrmuchii <n-1; i++){
        int rad1 = opParc(M[i].x), rad2 = opParc(M[i].y);
        if(rad1!=rad2){
            T[rad1]=rad2;
            sol[nrmuchii++]={M[i].x, M[i].y};
            sum+=M[i].cost;
        }
    }

}

int main()
{

    f>>n>>m;
    init();
    for(int i=1; i<=m; i++){
        f>>M[i].x>>M[i].y>>M[i].cost;
    }
    sort(M+1, M+m+1);
    solve();
    g<<sum<<'\n'<<n-1<<'\n';
    for(int i=0; i<n-1; i++)
        g<<sol[i].x<<" "<<sol[i].y<<'\n';
    return 0;
}