#include <bits/stdc++.h>
#define Nmax 200001
using namespace std;
ifstream f("apm.in"); ofstream g("apm.out");
struct muchie {int x,y,c;} v[400001];
int a[Nmax],b[Nmax],T[Nmax],R[Nmax];
bool cmp(muchie a, muchie b)
{   return a.c<b.c;}
int findR(int x)
{   int q=x;
    while(q!=T[q]) q=T[q];      ///merg in sus pe arbore
    while(x!=T[x]) {int y=T[x]; T[x]=q; x=y;}  /// compresia drumurilor
    return q;
}
void uneste(int x, int y)
{   if(R[x]>R[y]) T[y]=x; else T[x]=y; /// unesc arb. cu rang mai mic de cel cu rang mai mare
    if (R[x]==R[y]) R[y]++; /// maresc rangul arb. rezultat cu 1
}
int main()
{   int n,m;
    f>>n>>m;
    for(int i=1;i<=m;i++) f>>v[i].x>>v[i].y>>v[i].c;
    sort(v+1,v+m+1,cmp);
    for(int i=1;i<=n;i++) {T[i]=i; R[i]=1;}
    int s=0,k=0;
    for(int i=1;k<n-1;i++)
        if(findR(v[i].x)!=findR(v[i].y))
        {   k++; a[k]=v[i].x; b[k]=v[i].y; s=s+v[i].c;
            uneste(findR(a[k]),findR(b[k]));
        }
    g<<s<<'\n'<<k<<'\n';
    for(int i=1;i<=k;i++) g<<a[i]<<" "<<b[i]<<"\n";
    g.close(); f.close(); return 0;
}