#include <iostream>
#include <vector>
#include <set>
#include <fstream>
#include <algorithm>
#define nmax 200001
#define mmax 400001
using namespace std;
int tata[200001];
int h[200001];
int cost;
vector <pair <int, int> > v1;
struct nod {int x, y, c;};
bool cmp(nod a, nod b)
{
    return (a.c < b.c);
}
nod v[nmax];
int find (int x)
{
    int r=x;
    while (tata[r]) r=tata[r];
    int y=x, t;
    while (y!=r)
    {
        t=tata[y];
        tata[y]=r;
        y=t;
    }
    return r;
}

void unire(int x, int y)
{
    if (h[x]>h[y]) tata[y]=x;
    else {tata[x]=y; if (h[x]==h[y]) h[y]++; }
}


int main()
{

ifstream f("apm.in");
ofstream g("apm.out");
 int x, y, c, n, i, m;
    f >> n >> m;
for (i=1; i<=m; ++i)

{
    f >> v[i].x >> v[i].y >> v[i].c;

}
sort (v+1,v+m+1,cmp);

for (i=1; i<=m; ++i)
{
   int x1, x2, co;
   x1=v[i].x;
   x2=v[i].y;
   co=v[i].c;
   int q1=find(x1), q2=find(x2);
   if (q1!=q2) {cost+=co;unire(q1,q2);v1.push_back(make_pair(x1,x2));}

}

g << cost<<"\n";
g << n-1 << "\n";
vector <pair <int, int> > :: iterator it;
for (it=v1.begin();it!=v1.end();++it)
{
    g << (*it).first << " " << (*it).second << "\n";
}
    return 0;
}