/*
    Alg lui Boruvka/Sollin
    O(MlogN)
*/
#include <fstream>
#include <vector>
using namespace std;

#define pb push_back
#define mp make_pair
#define vf first
#define cost second

const int NMAX=200002;
const int Inf=0x3f3f3f3f;

vector< pair<int,int> > G[NMAX];
int N,M,t[NMAX],nr[NMAX];

int find(int x)
{
    if (x == t[x]) return x;
    return t[x]=find(t[x]);
}

void unite(int x,int y)
{
     x=find(x);y=find(y);
     if (nr[x] > nr[y])
        t[y]=x,nr[x]+=nr[y];
     else
        t[x]=y,nr[y]+=nr[x];
}

struct muchie
{
       int x,y,cost;
} E[NMAX]; // nearest neighbor

int Solx[NMAX],Soly[NMAX],z,CostMin;

void Boruvka()
{
    int i;
    for (i=1;i<=N;++i) t[i]=i,nr[i]=1;
    int nrmax=1;
    vector< pair<int,int> >::iterator it;
    
    while (nrmax < N)
    {
          for (i=1;i<=N;++i) E[i].cost=Inf;
          for (i=1;i<=N;++i)
            for (it=G[i].begin();it!=G[i].end();++it)
              if (find(it->vf) != find(i))
              {
                if (E[find(i)].cost > it->cost)
                {
                     E[find(i)].x=i;
                     E[find(i)].y=it->vf;
                     E[find(i)].cost=it->cost;
                }
              }
          for (i=1;i<=N;++i)
            if (E[i].cost < Inf)
            {
               if (find(E[i].x) == find(E[i].y)) continue;
               Solx[++z]=E[i].x;
               Soly[z]=E[i].y;
               CostMin+=E[i].cost;
               unite(E[i].x,E[i].y);
               nrmax=max(nrmax,nr[find(E[i].x)]);
            }                   
    }
}

int main()
{
    int i,j,k;
    ifstream fin("apm.in");
    fin>>N>>M;
    while (M--)
    {
          fin>>i>>j>>k;
          G[i].pb(mp(j,k));
          G[j].pb(mp(i,k));
    }
    
    Boruvka();
    
    ofstream fout("apm.out");
    fout<<CostMin<<'\n'<<z<<'\n';
    for (i=1;i<=z;++i) fout<<Solx[i]<<' '<<Soly[i]<<'\n';
    
    return 0;
}