#include <fstream>
#include <algorithm>

using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

#define MAXN 200000
#define MAXM 400000

struct apm {
    int x, y, c;
}v[MAXM];

bool cmp(apm a, apm b)
{
    return a.c<b.c;
}

int parent[MAXN+1];
int ans[MAXN+1][2];

int findp(int x)
{
    if(parent[x]==x) return x;
    return parent[x]=findp(parent[x]);
}

void unite(int x, int y)
{
    x=findp(x);
    y=findp(y);
    parent[x]=y;
}

int main() {
    int n, m;
    cin>>n>>m;
    int i;
    for(i=1; i<=m; i++)
        cin>>v[i].x>>v[i].y>>v[i].c;
    sort(v+1, v+m+1, cmp);
    for(i=1; i<=n; i++)
        parent[i]=i;
    int minns, poz;
    minns=poz=0;
    for(i=1; i<=m; i++)
    {
        if(findp(v[i].x)!=findp(v[i].y))
        {
            unite(v[i].x, v[i].y);
            minns+=v[i].c;
            ans[poz][0]=v[i].x;
            ans[poz][1]=v[i].y;
            poz++;
        }
    }
    cout<<minns<<'\n'<<poz<<'\n';
    for(i=0; i<poz; i++)
        cout<<ans[i][0]<<" "<<ans[i][1]<<'\n';
}