#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define buffs 1048576
FILE*f=freopen("apm.in","r",stdin);
FILE*g=freopen("apm.out","w",stdout);
struct gigi{int a,b,c;}v[400002];
char buff[buffs];
int tt[200002],rg[200002],pos=0,n,m,i,x,y,s=0;
std::vector<int>sol;
inline void read(int &nr)
{
    nr=0;
    while(buff[pos]<'0'||buff[pos]>'9') if(++pos==buffs)fread(buff,1,buffs,stdin),pos=0;
    int semn=1;
    if(buff[pos-1]=='-') semn=-1;
    while(buff[pos]>='0'&&buff[pos]<='9')
    {
        nr=(nr<<1)+(nr<<3)+buff[pos]-48;
        if(++pos==buffs)fread(buff,1,buffs,stdin),pos=0;
    }
    nr*=semn;
}
struct cmp{   bool operator () (gigi a,gigi b) { return a.c<b.c; }};
inline int ffa(int x)
{
    int z,zz;
    for(z=x;z!=tt[z];z=tt[z]);
    for(;x!=tt[x];)
    {
        zz=tt[x];
        tt[x]=z;
        x=zz;
    }
    return z;
}
inline void unite(int x,int y)
{
    if(rg[x]>rg[y]) tt[y]=x;
    else tt[x]=y;
    if(rg[x]==rg[y]) rg[y]++;
}
int main()
{fread(buff,1,buffs,stdin),pos=0;
read(n);read(m);
for(i=1;i<=m;i++)
{
    read(v[i].a);read(v[i].b);read(v[i].c);
}
for(i=1;i<=n;i++)
    tt[i]=i,rg[i]=1;
    sort(v+1,v+1+m,cmp());
for(i=1;i<=m;i++)
{
    x=ffa(v[i].a);y=ffa(v[i].b);
    if(x!=y) {unite(x,y);s+=v[i].c;sol.push_back(i);}
}

printf("%d \n",s);
x=sol.size();
printf("%d \n",x);
for(i=0;i<x;i++)
    printf("%d %d\n",v[sol[i]].a,v[sol[i]].b);
}