#include <fstream>
#include <algorithm>
#define NMax 200005
#define edgeMax 400005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int N,M;
int R[NMax], Depth[NMax];
struct Edge{
    int x, y, cost;
    bool use;
} E[edgeMax];
void init(){
    for(int i = 1; i <= N; i++)
        R[i] = i, Depth[i] = 1;
}

int findTrueRepr(int x){
    int init = x;

    while(R[R[x]] != R[x]){
        x = R[x];
    }

    x=R[x];
    while(R[init] != x){
        int next = R[init];
        R[init] = x;
        init = next;
    }

    return x;
}

bool areFromTheSameSet(int x, int y){
    return findTrueRepr(x) == findTrueRepr(y);
}

void unite(int x, int y){
    int rx = findTrueRepr(x);
    int ry = findTrueRepr(y);
    if(rx == ry)
        return;
    if(Depth[rx] > Depth[ry])
        R[ry] = rx;
    if(Depth[rx] < Depth[ry])
        R[rx] = ry;
    if(Depth[rx] == Depth[ry]){
        R[rx] = ry;
        Depth[ry] += 1;
    }
}
bool compareEdgesByCost(Edge a, Edge b){
    if(a.cost < b.cost)
        return true;
    else
        return false;
}

int main()
{
    long long i,c=0,s=0;
    fin>>N>>M;
    init();
    for(i=1;i<=M;i++)
        fin>>E[i].x>>E[i].y>>E[i].cost;
    sort(E+1,E+M+1,compareEdgesByCost);
    for(i=1;i<=M;i++)
    {
        if(!areFromTheSameSet(E[i].x,E[i].y))
        {
            unite(E[i].x,E[i].y);
            E[i].use=true;
            c+=E[i].cost;
            s+=1;
        }
    }
    fout<<c<<"\n"<<s<<"\n";
    for (i=1;i<=M;i++)
        if(E[i].use)
            fout<<E[i].x<<" "<<E[i].y<<"\n";
    return 0;
}