#include <bits/stdc++.h>
#define pb push_back
#define ll long long int
using namespace std;

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


const int DMAX = 2e5+10;

int tata[DMAX];
int costmin;
int n,m;
struct muchie{int x;int y; int c;
    friend bool operator>(muchie, muchie);

};
bool operator >(muchie a, muchie b)
 {
     return a.c>b.c;
 }
priority_queue<muchie, vector<muchie>,greater<muchie> >H;

vector<muchie> sol;

void unire(int x,int y);
int comp(int x);
void citire();
void kruskal();
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t,i,op,x,y;
    citire();
    kruskal();
    fout<<costmin<<'\n'<<n-1<<'\n';
    for(int i=0;i<sol.size();i++)
          fout<<sol[i].x<<" "<<sol[i].y<<'\n';

    return 0;
}
void citire()
{muchie a;
int i;
 fin>>n>>m;
  for(i=1;i<=m;i++)
    {
      fin>>a.x>>a.y>>a.c;
       H.push(a);
    }
}
int comp(int x){
    int root = x;
    while(tata[root])
        root = tata[root];

    int aux;
    while (tata[x]) {
        aux = tata[x];
        tata[x] = root;
        x = aux;
    }
    return root;
}
void unire(int x,int y){
    x=comp(x);
    y=comp(y);
    tata[x]=y;
}
void kruskal()
{
 int nrsel=0;
 while(nrsel!=n-1)
    {
      muchie a;
      a=H.top(); H.pop();

      if(comp(a.x) ==comp(a.y) )
          ;
          else
      {unire(a.x,a.y);
      nrsel++;
      costmin+=a.c;
      sol.pb(a);
      }
    }

}