#include <fstream>
#include <algorithm>
#define DIM 200001
#define x first
#define y second.first
#define z second.second
using namespace std;
ifstream fi("apm.in");
ofstream fo("apm.out");
int n,m;
pair<int,pair<int,int> > M[400001];
pair<int,int> R[DIM];
int P[DIM];
int cost,r;
int radacina(int a)
{
    if(P[a]==0)
        return a;
    P[a]=radacina(P[a]);
    return P[a];
}
int main()
{
    fi>>n>>m;
    for(int i=1;i<=m;i++)
        fi>>M[i].y>>M[i].z>>M[i].x;
    sort(M+1,M+m+1);
    /*
    for(int i=1;i<=m;i++)
        fo<<M[i].x<<" "<<M[i].y<<" "<<M[i].z<<"\n";
        */
    for(int i=1;i<=m;i++)
    {
        int a=M[i].y,b=M[i].z;
        int ra=radacina(a),rb=radacina(b);
        if(ra!=rb)
            P[rb]=ra,cost+=M[i].x,R[++r]=make_pair(a,b);
    }
    fo<<cost<<"\n"<<r<<"\n";
    for(int i=1;i<=r;i++)
        fo<<R[i].first<<" "<<R[i].second<<"\n";
    fi.close();
    fo.close();
    return 0;
}