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


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

int N, M, ArbX[nmax], ArbY[nmax], sol, X, Y, C, used[nmax], remainingNodes, crtNode;
vector<pair<int, int> > G[nmax];
priority_queue<muchie, vector<muchie>, greater<muchie> > Q;


void APM();

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    int i;
    scanf("%i %i", &N, &M);
    for(; M; M --)
    {
          scanf("%i %i %i", &X, &Y, &C);
          G[X].pb(mp(Y, C));
          G[Y].pb(mp(X, C));
    }
    remainingNodes = N - 1;
    APM();
    printf("%i\n", sol);
    printf("%i\n", crtNode);
    for(int i = 1; i <= crtNode; i++) printf("%i %i\n", ArbX[i], ArbY[i]);
    scanf("%i", &i);
    return 0;
}

void APM()
{
     int node = 1;
     used[node] = 1;
     vector<pair<int, int> > :: iterator it;
     while(remainingNodes)
     {
                  for(it = G[node].begin(); it != G[node].end(); ++it)
                         if(!used[it -> first])
                                     Q.push(mp(it -> second, mp(node, it -> first)));
                  muchie old = Q.top(); Q.pop();
                  while(used[old.second.second]) old = Q.top(), Q.pop();
                  sol += old.first;
                  ArbX[++ crtNode] = old.second.first;
                  ArbY[crtNode] = old.second.second;
                  node = old.second.second;
                  used[node] = 1;
                  remainingNodes --;
     }
}