///algoritmul lui Prim O(n^2)

#include <bits/stdc++.h>

using namespace std;

ifstream fin ("apm.in");
ofstream fout ("apm.out");

const int N=200001;
const int M=400001;
const int oo=1e9;

int n,m;
vector <pair<int,int>> G[N]; ///liste de adiacenta
int costAPM;
int d[N]; ///d[i]=distanta minima de la nodul i la unul dintre nodurile
          ///adaugate deja la apm
bool vis[N];
int tata[N];

void Citire()
{   int x,y,cost;
    fin>>n>>m;
    for(int i=1; i<=m; i++)
        {fin>>x>>y>>cost;
         G[x].push_back({y,cost});
         G[y].push_back({x,cost});
        }

}

///initializam vectorul de dist minime cu cea mai mare val posibila (oo)
void Initializare()
{
    for(int i=1; i<=n; i++)
        d[i]=oo;
}

void Prim()
{ Initializare();
  d[1]=0; ///nodul de start este 1
  for(int i=1; i<=n; i++) /// se adauga pe rand cate un nod la APM
    { ///cautam nodul cu distanta minima
      int node, dmin=oo;
      for(int j=1; j<=n; j++)
        if(vis[j]==0 && d[j]<dmin)
           node=j,dmin=d[j];
      vis[node]=1;
      costAPM+=dmin;
      /// reactualizam vectorul d pt nodurile neselectate folosind noul nod adaugat
      for(auto x : G[node])
        if(vis[x.first]==0 && d[x.first]>x.second)
              { d[x.first]=x.second;
                tata[x.first]=node;
              }
    }
}

void Afisare()
{
    fout<<costAPM<<"\n";
    fout<<n-1<<"\n";
    for(int i=2; i<=n; i++)
        fout<<i<<" "<<tata[i]<<"\n";
}
int main()
{
    Citire();
    Prim();
    Afisare();
    return 0;
}