#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
#define M 400005
#define N 200005
int n,m,x[M],y[M],c[M],v[M],u[N],rez,k,w[M];
void reuniune(int a,int b)
{
    for(int i=1;i<=n;i++)
        if(u[i]==b)
        u[i]=a;
}
int cmp(int a, int b)
{
    return (c[a]<c[b]);
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=n;i++)
        u[i]=i;
    for(int i=1;i<=m;i++)
    {
        f>>x[i]>>y[i]>>c[i];
        v[i]=i;
    }
    sort(v+1,v+1+m,cmp);
    for(int i=1;i<=m;i++)
        if(u[x[v[i]]]!=u[y[v[i]]])
        {
            rez+=c[v[i]];
            reuniune(u[x[v[i]]],u[y[v[i]]]);
            w[++k]=v[i];
        }
    g<<rez<<"\n";
    g<<k<<"\n";
    for(int i=1;i<=k;i++)
        g<<y[w[i]]<<" "<<x[w[i]]<<"\n";
}