#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct muchie
{
    int x;
    int y;
    int c;
};
vector <muchie> M;
vector < pair <int, int> > V;
int t[200005],n,m,i,cost,r1,r2,marime,nr;
bool cmp(muchie a, muchie b)
{
    return (a.c<b.c);
}
int radacina(int a)
{
    if (t[a]!=a) t[a]=radacina(t[a]);
    return t[a];
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d",&n,&m);
    for (i=1; i<=m; i++)
    {
        muchie muchie1;
        scanf("%d %d %d",&muchie1.x,&muchie1.y,&muchie1.c);
        M.push_back(muchie1);
    }
    sort(M.begin(),M.end(),cmp);
    for (i=1; i<=n; i++) t[i]=i;
    cost=0;
    nr=n;
    for (i=0; i<m; i++)
    {
        r1=radacina(M[i].x);
        r2=radacina(M[i].y);
        if (r1!=r2)
        {
            nr--;
            cost+=M[i].c;
            V.push_back(make_pair(M[i].x,M[i].y));
            t[r2]=r1;
        }
        if (nr==n) break;
    }
    printf("%d\n",cost);
    marime=V.size();
    printf("%d\n",marime);
    for (i=0; i<marime; i++) printf("%d %d\n",V[i].first, V[i].second);
    return 0;
}