#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#include<bitset>
#define INF 0x3f3f3f3f
#define mp make_pair
#define pb push_back
#define maxn 200010
#define maxm 400010
using namespace std;
int TT[maxn],RG[maxn],n,m,i,x,y,op,cost;
vector < pair < int, int > > sol;
struct elem { int x, y, c; } P[maxm];

int cmp(elem a, elem b)
{
    return (a.c<b.c);
}

int find(int x)
{
    int R, y;
    for(R=x;R!=TT[R];R=TT[R]);
    while(TT[x]!=x)
    {
        y=TT[x];
        TT[x]=R;
        x=y;
    }
    return R;
}

void unite(int x, int y)
{
    if(RG[x] > RG[y]) TT[y] = x;
    else TT[x] = y;

    if(RG[x] == RG[y])
        RG[y]++;
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1; i<=n; ++i)
        RG[i] = 1, TT[i] = i;
    for(i=1; i<=m; ++i)
        scanf("%d%d%d",&P[i].x,&P[i].y,&P[i].c);
    sort(P+1, P+m+1, cmp);
    for(i=1; i<=m; ++i)
    {
        if(find(P[i].x)!=find(P[i].y))
            unite(find(P[i].x), find(P[i].y)), cost+=P[i].c, sol.push_back(make_pair(P[i].x, P[i].y));
    }
    printf("%d\n%d\n",cost,sol.size());
    for(i=0; i<sol.size(); ++i)
        printf("%d %d\n",sol[i].first, sol[i].second);
    return 0;
}