#include <stdio.h>
#include <algorithm>
#define nmax 200010
using namespace std;
struct date1 { int x,y,z; };
struct date2 { int x,y; };
int n,m,i,j,nr,rang[nmax],sz[nmax],tata[nmax],sum;
date1 t[nmax];
date2 sol[nmax];
bool cmp(const date1 &x,const date1 &y) { return (x.z<y.z); }
int root(int x)
{
    if (x==tata[x]) return x; else
        return tata[x]=root(tata[x]);
}
void unite(int x,int y)
{
    x=root(x); y=root(y);
    if (x!=y) {
        if (rang[x]>rang[y]) {
            tata[y]=x; sz[y]=sz[y]+sz[x];
        } else {
            tata[x]=y; sz[x]=sz[x]+sz[y];
        }
        if (rang[x]==rang[y]) rang[y]++;
    }
}
int main() {
freopen("apm.in","r",stdin);
freopen("apm.out","w",stdout);
scanf("%d %d",&n,&m);
for (i=1;i<=m;i++) scanf("%d %d %d",&t[i].x,&t[i].y,&t[i].z);
sort(t+1,t+m+1,cmp);
for (i=1;i<=n;i++) { rang[i]=0; sz[i]=1; tata[i]=i; }
for (i=1;i<=m;i++)
    if (root(t[i].x)!=root(t[i].y)) {
       sum=sum+t[i].z; nr++; sol[nr].x=t[i].x; sol[nr].y=t[i].y;
       unite(t[i].x,t[i].y);
    }
printf("%d\n%d\n",sum,nr);
for (i=1;i<=nr;i++) printf("%d %d\n",sol[i].x,sol[i].y);
return 0;
}