#include <bits/stdc++.h>
#define N 200005
#define pb push_back
#define INF 0x3f3f3f3f

using namespace std;

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

int n,m,u,s;
vector<pair<int,int> >g[N];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >Q;
void read(){
  int x,y,z;
  fin>>n>>m;
  for(int i=1;i<=m;++i){
    fin>>x>>y>>z;
    g[x].pb({y,z});
    g[y].pb({x,z});
  }
}
void Prim(int x){
  vector<int>key(N,INF);
  vector<int>f(N,0);
  bitset<N>mrk;
  Q.push({0,x});
  key[x]=0;
  while(!Q.empty()){
    u=Q.top().second;
    Q.pop();
    mrk[u]=1;
    for(auto y:g[u]){
       int v=y.first,cost=y.second;
       if(!mrk[v] && key[v]>cost){
        key[v]=cost;
        Q.push({key[v],v});
        f[v]=u;
       }
    }
  }
  for(int i=1;i<=n;++i)
     s+=key[i];
  fout<<s<<"\n";
  fout<<n-1<<"\n";
  for(int i=1;i<=n;++i)
     if(i!=x){
    fout<<f[i]<<" "<<i<<"\n";
    }
}
int main(){
 read();
 Prim(1);
 return 0;
}