#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

int v[400001]={0};
int dad[200001]={0};
vector<int> stack;

struct arcu{
    int a, b, cost;
}arc[400001]={0};

bool cmp(arcu a1, arcu a2){
    return (a1.cost<a2.cost);
}

int find_dad(int nod){

     int dad;
    stack.push_back(nod);
    while(nod != ::dad[nod]){
        stack.push_back(::dad[nod]);
        nod = ::dad[nod];

    }
    dad = ::dad[nod];
    while(!stack.empty()){
        nod = stack.back();
        stack.pop_back();
        ::dad[nod] = dad;
    }
    return dad;
}

char buff[200000];int pos=0, semn;
FILE*f=freopen("apm.in","r",stdin);
FILE*g=freopen("apm.out","w",stdout);
inline void read(int &nr){
    semn = 1;
    while(buff[pos] < '0' || buff[pos] > '9'){if(buff[pos]== '-' )semn = -1; if(++pos == 200000) fread(buff, 1, 200000, stdin), pos = 0;}
    nr = 0;
    while('0' <= buff[pos] && buff[pos] <= '9') {nr = nr * 10 + buff[pos] - '0';if(++pos == 200000) fread(buff, 1, 200000, stdin), pos = 0;}
    nr*=semn;
}
char buf[2000]="";
int lg = 0;
void scrie(int a, int b){

    lg += sprintf(buf + lg,"%d %d\n", a, b);
    if(lg > 199992) fwrite(buf, lg, 1, stdout), lg = 0;
}

int main()
{
    fread(buff, 1, 200000, stdin);
    int i, j, n, m, op, a, b, ta, tb, cost=0, lg=0;
    read(n);
    read(m);
    for(i=1;i<=m;i++){

        read(arc[i].a);read(arc[i].b);read(arc[i].cost);
    }

    for(i=1;i<=n;i++)
        dad[i]=i;

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

    for(i=1;i<=m;i++)
    {
        ta=find_dad(arc[i].a);
        tb=find_dad(arc[i].b);
        if(ta!=tb)
        {
            cost+=arc[i].cost;
            v[++lg]=i;
            dad[ta]=tb;
            if(lg>=(n-1))
                break;
        }
    }
    ::lg = sprintf(buf + ::lg, "%d\n%d\n", cost, lg);
    for(i=1;i<n;i++){
        scrie(arc[v[i]].a, arc[v[i]].b);
    }
    fwrite(buf, ::lg, 1, stdout);
}