#include<fstream>
#include<algorithm>
#include<vector>
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];
vector<int>s[N];
void reuniune(int a,int b)
{
    int l1=s[a].size(),l2=s[b].size();
    if(l1>=l2)
    {
        for(int i=l2-1;i>=0;i--)
        {
            s[a].push_back(s[b][i]);
            u[s[b][i]]=a;
            s[b].pop_back();
        }
    }
    else
    {
        for(int i=l1-1;i>=0;i--)
        {
            s[b].push_back(s[a][i]);
            u[s[a][i]]=b;
            s[a].pop_back();
        }
    }

}
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;
        s[i].push_back(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";
}