#include <bits/stdc++.h>
#define N_MAX 200005
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int n,m,nr,val,tata[N_MAX];
struct lat{
    int x;
    int y;
    int val;
};
struct par{
    int x;
    int y;
};
bool cmp(lat x1, lat x2)
{
    return x1.val<x2.val;
}
lat hop[N_MAX*2];
par sol[N_MAX];
int tata_mare(int node)
{
    int r=node;
    while(tata[r]!=r) r=tata[r];
    while(tata[node]!=node)
    {
        int y=tata[node];
        tata[node]=r;
        node=y;
    }
    return r;
}
int main()
{
    in >> n >> m;
    for(int i=1; i<=n; i++)
        tata[i]=i;
    for(int i=1; i<=m; i++)
    {
        in >> hop[i].x >> hop[i].y >> hop[i].val;
    }
    sort(hop+1,hop+m+1,cmp);
    for(int i=1; i<=m; i++)
    {
        if(nr==n-1)
            break;
        int x=tata_mare(hop[i].x);
        int y=tata_mare(hop[i].y);
        if(x!=y)
        {
            tata[y]=x;
            nr++;
            sol[nr].x=hop[i].x;
            sol[nr].y=hop[i].y;
            val+=hop[i].val;
        }
    }
    out << val << '\n';
    out << nr << '\n';
    for(int i=1; i<n; i++)
    {
        out << sol[i].y << ' ' << sol[i].x << '\n';
    }
    return 0;
}