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

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

int N, M, X, Y, C, remainingNodes, minCost, used[nmax];
vector<pair<int, int> > G[nmax], Arb;
priority_queue<edge, vector<edge>, greater<edge> > Q;

void APM();


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

void APM()
{
     vector<pair<int, int> > :: iterator it;
     int node = 1, end, cost;
     used[1] = 1;
     while(remainingNodes > 0)
     {
                          for(it = G[node].begin(); it != G[node].end(); ++it)
                                 if(!used[it -> first])
                                 {
                                             end = it -> first;
                                             cost = it -> second;
                                             Q.push(mp(cost, mp(node, end)));
                                 }
                          edge old = Q.top(); Q.pop();
                          while(used[old.second.second]) 
                                  old = Q.top(), Q.pop();
                          Arb.pb(mp(old.second.first, old.second.second));
                          used[old.second.second] = 1;
                          node = old.second.second;
                          remainingNodes --;
                          minCost += old.first;
     }
}