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

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

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

void afis()
{
    int i;
    fout<<apm<<'\n'<<n-1<<'\n';
    for(i=1; i<n; i++) fout<<g[a[i]].x<<' '<<g[a[i]].y<<'\n';
}

int main()
{
    int i, j, mn, mx;
    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++) c[i]=i;
    sort(g+1,g+m+1,cmp);
    k=0;
    for(i=1; k<(n-1); i++)
        if(c[g[i].x]!=c[g[i].y]) ///nu alegem o muchie din cadrul aceleiasi componente conexe
        {
            a[++k]=i;
            apm+=(long long)g[i].c;
            mn=min(c[g[i].x],c[g[i].y]), mx=max(c[g[i].x],c[g[i].y]);
            for(j=1; j<=n; j++)
                if(c[j]==mx) c[j]=mn;
        }
    afis();
    return 0;
}