#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <utility>
#include <queue>
using namespace std;


#define nmax 200010
#define muchie pair<long,pair<long,long> >
#define pb push_back
#define mp make_pair

priority_queue< muchie, vector<muchie>, greater<muchie> > q;
vector<pair<long,long> > nodes[nmax];
struct edge
{
       int a,b;
};
vector<edge> arb;
vector<long> used(nmax);
long n,m,x,y,c,sum=0;

void read_input()
{
     scanf("%ld %ld", &n,&m);
     for(int i=0;i<m;i++)
     {
             scanf("%ld %ld %ld", &x,&y,&c);
             nodes[x].pb(mp(y,c));
             nodes[y].pb(mp(x,c));
     }
}

int folosit()
{
     for(int i=1;i<=n;i++) if(used[i]==0) return 1;
     return 0;
}

void Prim()
{
     int node=1;
     used[node]=1;
     while(folosit())
     {
                     for(int i=0;i<nodes[node].size();i++)
                     {
                              if(used[nodes[node][i].first]==0)
                              {
                                                        long costt=nodes[node][i].second;
                                                        long endd=nodes[node][i].first;
                                                        q.push(mp(costt,mp(node,endd)));
                              }
                     }
                     muchie old=q.top();
                     q.pop();
                     while(used[old.second.second]==1)
                     {
                                                      old=q.top();
                                                      q.pop();
                     }
                     sum+=old.first;
                     edge New;
                     New.a=old.second.first;
                     New.b=old.second.second;
                     arb.pb(New);
                     node=old.second.second;
                     used[node]=1;
     }
     printf("%ld\n", sum);
     printf("%ld\n", arb.size());
     for(int i=0;i<arb.size();i++) printf("%ld %ld\n", arb[i].a,arb[i].b);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int i;
    read_input();
    Prim();
  //  scanf("%i", &i);
    return 0;
}