#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct Node{
    int rnk, dad;
}a[200002];
struct Muchie{
    int x, y, c;
}g[400002];
int n, m, k, s[200002];
long long apm;

inline bool cmp(const Muchie A, const Muchie B){
    return A.c<B.c;
}

int rad(int nod)
{
    int init=nod, x=a[nod].dad;
    while(nod!=x)
    {
        nod=x;
        x=a[x].dad;
    }
    a[init].dad=x;
    return x;
}

void join(int p, int q)
{
    int pp=rad(p), qq=rad(q);
    if(a[pp].rnk==a[qq].rnk) a[pp].dad=qq, a[qq].rnk++;
    else if(a[pp].rnk<a[qq].rnk) a[pp].dad=qq;
    else a[qq].dad=pp;
}

int main()
{
    int i;
    fin>>n>>m;
    for(i=1; i<=m; i++) fin>>g[i].x>>g[i].y>>g[i].c;
    for(i=1; i<=n; i++) a[i].dad=i;
    sort(g+1,g+m+1,cmp);
    for(i=1; k<(n-1); i++)
        if(rad(g[i].x)!=rad(g[i].y))
        {
            s[++k]=i;
            apm+=(long long)g[i].c;
            join(g[i].x,g[i].y);
        }
    fout<<apm<<'\n'<<n-1<<'\n';
    for(i=1; i<n; i++) fout<<g[s[i]].x<<' '<<g[s[i]].y<<'\n';
    return 0;
}