#include<fstream>
#include<vector>
#include<queue>
#define maxN 200001
#define maxM 400001
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct nod{
    int inf,c;
};
struct coord{
    int x,y,co;
};
struct cmp{
    bool operator() ( coord a,coord b)
    {
        return a.co>b.co;
    }
};
vector<nod>v[maxN];
priority_queue<coord,vector<coord>,cmp>heap;
int n,m,sol,t[maxN];
bool viz[maxN];
void citire()
{
    nod a;
    int p,q,r;
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>q>>p>>r;
        a.c=r;
        a.inf=q;v[p].push_back(a);
        a.inf=p;v[q].push_back(a);
    }
}
void proceseaza(int nod_start)
{
    for(int i=0;i<v[nod_start].size();i++)
        if(viz[v[nod_start][i].inf]==false)
        {
            coord aux;
            aux.x=nod_start;
            aux.y=i;
            aux.co=v[nod_start][i].c;
            heap.push(aux);
        }
}
void prim()
{
    coord a;
    int i,j;
  proceseaza(1);
  viz[1]=true;
  for(int k=1;k<n;k++)
  {
      a=heap.top();
        i=a.x;
        j=a.y;
      while(viz[v[i][j].inf]==true)
      {
          heap.pop();
          a=heap.top();
          i=a.x;
          j=a.y;
      }
      if(!heap.empty())
      {
          heap.pop();
          viz[v[i][j].inf]=true;
          sol+=a.co;
          t[v[i][j].inf]=i;
          proceseaza(v[i][j].inf);
      }
  }
}

void afisare()
{
     g<<sol<<'\n'<<n-1<<'\n';
    for(int i=2;i<=n;i++)
        g<<i<<" "<<t[i]<<'\n';
}
int main ()
{
    citire();
    prim();
    afisare();
    return 0;
}