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