#include <bits/stdc++.h>

using namespace std;

#define Nmax 400100

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

struct Valoros{

int x,y,c;

}v[Nmax];


int m,n,G[Nmax],sum;
vector < int > sol;

bool cmp(const Valoros A, const Valoros B){
    return (A.c < B.c);
}

int grup(int s){

    if(G[s] == s) return s;
    G[s] = grup(G[s]);
    return G[s];

}

void reunion(int s, int p){

    G[grup(s)]=grup(p);
}


int main()
{
    in>>n>>m;
    for(int i=1;i<=m;i++)
    {
        in>>v[i].x>>v[i].y>>v[i].c;
    }
    sort(v + 1 , v + m + 1, cmp);
    for(int i=1;i<=n;i++)
        G[i]=i;
    sum=0;
    for(int i=1 ;i <=m; i++)
        if(grup(v[i].x) != grup(v[i].y) )
            {   sum+=v[i].c;
                reunion(v[i].x,v[i].y);
                sol.push_back(i);
    }
    out<<sum<<'\n'<<n-1<<'\n';
    for(int i=0 ; i < sol.size(); i++)
        out<<v[sol[i]].x<<" "<<v[sol[i]].y<<'\n';


    return 0;
}