#include<fstream>
#include<vector>
#include<algorithm>
#define nmax 200005
#define mmax 400005
#define fill(v,n) for(i=1;i<=n;i++) v[i]=i;
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct NOD
{
    int x,y,c;
}nods[nmax];
int G[nmax],n,m,ans,ind[nmax];
vector<int> v;
bool cmp(int i,int j)
{
    return (nods[i].c<nods[j].c);
}
inline int grupa(int i)
{
    if(G[i]==i)
        return i;
    G[i]=grupa(G[i]);
    return G[i];
}
void un(int i,int j)
{
    G[grupa(i)]=grupa(j);
}
int main()
{
    f>>n>>m;
    int i;
    for(i=1;i<=m;i++)
        f>>nods[i].x>>nods[i].y>>nods[i].c;
    fill(ind,m);
    fill(G,n);
    sort(ind+1,ind+m+1,cmp);
    for(i=1;i<=m;i++)
        if(grupa(nods[ind[i]].x)!=grupa(nods[ind[i]].y))
        {
            ans+=nods[ind[i]].c;
            un(nods[ind[i]].x,nods[ind[i]].y);
            v.push_back(ind[i]);
        }
    g<<ans<<'\n';
    g<<n-1<<'\n';
    for(i=0;i<n-1;i++)
        g<<nods[v[i]].x<<' '<<nods[v[i]].y<<'\n';
    f.close();
    g.close();
    return 0;
}