#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int NMAX=200005;

int h[NMAX+5];
int t[NMAX+5];
struct muchii
{
    int u, v, c;
    bool ok;
};
vector<muchii>G;
bool cmp(muchii x, muchii y)
{
    return x.c<y.c;
}
int FindSet(int x)
{
      while(x!=t[x])
            x=t[x];
      return x;
}
void UnionSet(int x, int y)
{
    //x si y reprezinta radacinile arobrilor
    if(h[x]==h[y])
    {
        t[y]=x;
        h[x]++;
    }
    else
    {
       if(h[x]<h[y])
          t[x]=y;
       else
          t[y]=x;
    }

}


int main()
{
    int cost=0, n, m, i, tu, tv, nrm=0;
    fin>>n>>m;
    muchii a;
    for(i=1;i<=m;i++)
    {
        fin>>a.u>>a.v>>a.c;
        a.ok=0;
        G.push_back(a);
    }
    sort(G.begin(), G.end(), cmp);
    for(i=1;i<=n;i++)
    {
        t[i]=i;
        h[i]=1;
    }
    for(i=0;i<=m-1;i++)
    {
        a=G[i];
        tu=FindSet(a.u);
        tv=FindSet(a.v);
        if(tu!=tv)
        {
            UnionSet(tu, tv);
            G[i].ok=1;
            cost=cost+a.c;
            nrm=nrm+1;

        }
    }
    fout<<cost<<"\n";
    fout<<nrm<<"\n";
    for(i=0;i<=m-1;i++)
    {
        if(G[i].ok==1)
            fout<<G[i].u<<" "<<G[i].v<<"\n";
    }


    return 0;
}