#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

int n,m,i,t[200005],ct,s,val1,val2;
bool viz[500005];
struct muchie
{
    int x;
    int y;
    int cost;
}v[400005];

bool cmp(muchie a, muchie b)
{
    return a.cost<b.cost;
}
int find(int x)
{
    int y=x,val;
    while(t[x]!=x) x=t[x];
    while(x!=y)
    {
        val=y;
        y=t[y];
        t[val]=x;
    }
    return x;
}
int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    f>>n>>m;
    for(i=1;i<=m;i++)
        f>>v[i].x>>v[i].y>>v[i].cost;
    for(i=1;i<=n;i++)
        t[i]=i;
    sort(v+1,v+m+1,cmp);
    for(i=1;i<=m && ct<n-1;i++)
        if(find(v[i].x)!=find(v[i].y))
        {
            s=s+v[i].cost;
            val1=find(v[i].x);
            val2=find(v[i].y);
            t[val1]=val2;
            viz[i]=true;
            ct++;
        }
    g<<s<<"\n";
    g<<ct<<"\n";
    for(i=1;i<=m;i++)
        if(viz[i]==true)
        {
            g<<v[i].y<<" "<<v[i].x<<"\n";
        }
    return 0;
}