#include <stdio.h>
#include <vector>
#include<queue>

using namespace std;

struct graf{
    long x,y,d;
};

class compar
{
  public:
  bool operator()(graf a,graf b)
  {return a.d>b.d;}
};

priority_queue<graf,vector<graf>,compar> q;

vector<graf> v[200001];

long ok,aux,cost,nm,n,m,i,cp[200001];
graf nod;

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%ld %ld",&n,&m);
    for(i=1;i<=m;i++) {
        scanf("%ld %ld %ld",&nod.x,&nod.y,&nod.d);
        v[nod.x].push_back(nod);
        aux=nod.x;
        nod.x=nod.y;
        nod.y=aux;
        v[nod.x].push_back(nod);
    }
    nm=0;
    for(i=0;i<v[1].size();i++)
        q.push(v[1][i]);
    cp[1]=1;
    ok=1;
    while(nm<n-1) {
        nod=q.top();
        while (cp[nod.y]!=0) {
            q.pop();
            nod=q.top();
        }
        if(ok==1) {
            ok=0;
            cp[1]=nod.y;
        }

        cp[nod.y]=nod.x;
        cost+=nod.d;
        nm++;
        for(i=0;i<v[nod.y].size();i++)
            q.push(v[nod.y][i]);

    }
    printf("%ld\n%ld\n",cost,nm);
    for(i=1;i<=nm;i++)
        printf("%ld %ld\n",cp[i],i);
    return 0;
}