#include <bits/stdc++.h>

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
struct muchie{int x,y,c,ok;} a[400004];
int f[200002];

int getf(int i)
{
    if(f[i]==i)
        return i;
    f[i]=getf(f[i]);
    return f[i];
}

void unite(int a,int b)
{
    int r=rand()%2;
    a=getf(a);
    b=getf(b);
    if(r)
    {
        f[a]=b;
    }
    else
    {
        f[b]=a;
    }
}

bool cmp(muchie a, muchie b)
{
    return (a.c<b.c);
}
int main()
{int n,m,i,j,sol=0,cnt=0;
srand(time(NULL));
in>>n>>m;
for(i=1;i<=n;i++)
    f[i]=i;
for(i=1;i<=m;i++)
{
    in>>a[i].x>>a[i].y>>a[i].c;
}
sort(a+1,a+m+1,cmp);

for(i=1;i<=m;i++)
{
    if(getf(a[i].x)!=getf(a[i].y))
    {
        sol+=a[i].c;
        unite(a[i].x,a[i].y);
        cnt++;
        a[i].ok=1;
    }
    if(cnt==n-1)
        i=m+2;
}
out<<sol<<'\n';
out<<n-1<<'\n';
for(i=1;i<=m;i++)
{
    if(a[i].ok==1)
        out<<a[i].x<<" "<<a[i].y<<'\n';
}
    return 0;
}