#include <iostream>
#include<vector>
#include<fstream>
#include<algorithm>
using namespace std;
struct M
{
    int x,y,c;
}v[400001];
bool compare(M a,M b)
{
    return(a.c<b.c);
}
int gr[400001],i,j,n,m,k,c,h,x,y;
vector<int>a;
int grupa(int i)
{
    if(gr[i]==i)return i;
    gr[i]=grupa(gr[i]);
    return gr[i];
}
int main()
{
    ifstream f("apm.in");
    f>>n>>m;
    for(i=0;i<m;++i)
    {
        f>>v[i+1].x>>v[i+1].y>>v[i+1].c;
    }
    f.close();
    sort(v+1,v+1+m,compare);
    ++m;
    for(i=1;i<m;++i)gr[i]=i;
    for(i=1;i<m;++i)
    {
        x=grupa(v[i].y);y=grupa(v[i].x);
        if(x!=y)
        {
            ++h;a.push_back(i);c+=v[i].c;
            //if(y>x)
                gr[y]=x;
           // else gr[x]=y;

        }
    }
    ofstream g("apm.out");
    g<<c<<'\n'<<h<<'\n';
    for(i=0;i<h;++i)
    {
        g<<v[a[i]].x<<" "<<v[a[i]].y<<'\n';
    }
    g.close();
    return 0;
}