#include <fstream>
#include <queue>
#include <vector>
using namespace std;

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

int nd[200001],rn[200001];
struct muchie{
    muchie(int a,int b,int c):x(a),y(b),price(c){}
    int x,y,price;
};
struct cmp{ bool operator()(const muchie &m1,const muchie &m2) {return m1.price>m2.price;} };

inline int find(int x)
{
    while(nd[x]!=x)
        x=nd[x];
    return x;
}

void unite(int x,int y)
{
    if(rn[x]>rn[y]) nd[y]=x;
    else nd[x]=y;

    if(rn[x]==rn[y]) rn[y]++;

    return;
}

int main()
{
    int n,m;
    priority_queue<muchie,vector<muchie>,cmp> pq;
    f>>n>>m;
    for(int i=1;i<=n;i++){
        nd[i]=i;
        rn[i]=1;
    }
    for(int i=1;i<=m;i++){
        int x,y,c;
        f>>x>>y>>c;
        pq.push(muchie(x,y,c));
    }

    vector<int> sl;
    int s=0;

    while(!pq.empty()){
        muchie mc=pq.top();
        pq.pop();
        if(find(mc.x)!=find(mc.y)){
            unite(find(mc.x),find(mc.y));
            s+=mc.price;
            sl.push_back(mc.x);
            sl.push_back(mc.y);
        }
    }

    g<<s<<'\n'<<sl.size()/2<<'\n';
    for(unsigned j=0;j<sl.size();j+=2)
        g<<sl[j]<<" "<<sl[j+1]<<'\n';

    return 0;
}