#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
struct Side{int e1, e2, cost;};
struct Nod{
    int ranq;
   int parent;
    };
Nod c[200005];
void makeset(int x){
c[x].parent=x;
c[x].ranq=0;
}
int findset(int x){
if (c[x].parent!=x) c[x].parent=findset(c[x].parent);
return c[x].parent;
}
void Union(int x, int y){
int xroot, yroot;
xroot=findset(x);
yroot=findset(y);
if (xroot!=yroot) {
if (c[xroot].ranq<c[yroot].ranq)
     c[xroot].parent=yroot;
else if (c[xroot].ranq>c[yroot].ranq)
    c[yroot].parent=xroot;
else {c[xroot].parent=yroot;
      c[yroot].ranq++;
}
}
return;
}
bool compare ( Side a, Side b)
{
  return (a.cost < b.cost );
}


Side Muchii[400005];
int A[200005];
int n,m;
int main()
{   ifstream fin("apm.in");
     ofstream fout("apm.out");

int nr=0;
    fin>>n>>m;
    for(int i=0; i<m; i++)
        fin>>Muchii[i].e1>>Muchii[i].e2>>Muchii[i].cost;
    for(int i=1; i<=n; i++)
        makeset(i);
    sort(Muchii, Muchii+m, compare);
    for(int i=0; i<m && nr<=n-1; i++)
        if(findset(Muchii[i].e1)!=findset(Muchii[i].e2)){
    Union(Muchii[i].e1,Muchii[i].e2);
       A[++nr]=i;
        }
        int cost=0;
        for(int i=1; i<n; i++)
    cost+=Muchii[A[i]].cost;
        fout<<cost<<endl;
        fout<<n-1<<endl;

    for(int i=1; i<n; i++)
  fout<<Muchii[A[i]].e2<<" "<<Muchii[A[i]].e1<<endl;
    return 0;
}