//Alg Prim
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
#define nod first
#define cost second
const int NMAX=200001,Inf=1<<30;
int N,M,key[NMAX],t[NMAX],sol;
vector< pair<int,int> > G[NMAX];
bitset<NMAX> u;
ifstream fin("apm.in");
ofstream fout("apm.out");
int h[NMAX],nr,poz[NMAX];
void Sift(int k){
     int Son;
     if (2*k<=nr){
       Son=2*k;
       if (Son<nr && key[h[Son]]>key[h[Son+1]])
         ++Son;
       if (key[h[k]]<key[h[Son]]) Son=0;
       }
     else Son=0;
     while (Son){
       poz[h[k]]=Son;poz[h[Son]]=k;
       int aux=h[k];h[k]=h[Son];h[Son]=aux;
       k=Son;
       if (2*k<=nr){
       Son=2*k;
       if (Son<nr && key[h[Son]]>key[h[Son+1]])
         ++Son;
       if (key[h[k]]<key[h[Son]]) Son=0;
       }
       else Son=0;
       }
     }
void Percolate(int k){
     int aux=h[k];
     while (k>1 && key[aux]<key[h[k/2]]){
           h[k]=h[k/2];
           poz[h[k]]=k;
           k/=2;}
     h[k]=aux;
     poz[h[k]]=k;
     }
void pop(){
     h[1]=h[nr--];
     poz[h[1]]=1;
     Sift(1);
     }
int main(){
    int i,j,k;
    vector< pair<int,int> >::iterator it;
    fin>>N>>M;
    while (M--){
      fin>>i>>j>>k;
      G[i].push_back(make_pair(j,k));
      G[j].push_back(make_pair(i,k));
      }
    nr=N;
    for (i=2;i<=N;++i)
      key[i]=Inf,h[i]=i,poz[i]=i,u[i]=1;
    key[1]=0;h[1]=1;
    while (nr>0){
       k=h[1];
       pop();
       u[k]=0;
       sol+=key[k];
       for (it=G[k].begin();it!=G[k].end();++it)
         if (u[it->nod] && key[it->nod]>it->cost)
           key[it->nod]=it->cost,t[it->nod]=k,Percolate(poz[it->nod]);
       }
    fout<<sol<<'\n';
    fout<<N-1<<'\n';
    for (i=2;i<=N;++i)
     fout<<i<<' '<<t[i]<<'\n';
    return 0;
}