// All rights reserved to me ..
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#define NMAX 200100
#define MMAX 400100
using namespace std;

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


struct cmp
{
    bool operator()(const pair<int, int> &A, const pair<int, int> &B)
    {
        return A.first > B.first;
    }
};


int N, M, dad[NMAX], co[NMAX];
vector< pair<int, int> > A[NMAX];
bool ap[MMAX];
priority_queue< pair<int, int>, vector< pair<int, int> >, cmp> PQ;
    int vertex = 1, mc = 0;
    vector< pair<int, int> > solution;

int main()
{
for (int i = 1; i < NMAX; ++i) co[i] = 2000000000;
	
    fin >> N >> M;
    for (int i = 1; i <= M; ++i)
    {
        int X, Y, cost;
        fin >> X >> Y >> cost;
        
        A[X].push_back(make_pair(cost, Y));
        A[Y].push_back(make_pair(cost, X));
    }
    
    // cost, nod
    PQ.push(make_pair(0, 1));
    co[1] = 0;
    ap[0] = true;
    for (int ii = 1; ii <= N; ++ii)
    {
        int nod = 0;
	  while (ap[nod])
	  {
		  nod = PQ.top().second;
		  PQ.pop();
	  }
        mc += co[nod];
        ap[nod] = true;
        
        for (vector< pair<int, int> >::iterator it = A[nod].begin(); it != A[nod].end(); ++it)
        {
            if (!ap[it->second] && it->first < co[it->second])
            {
                co[it->second] = it->first;
                dad[it->second] = nod;
                PQ.push(make_pair(it->first, it->second));
            }
        }
    }
    
    fout << mc << '\n';
    fout << N - 1 << '\n';
    
    for (int i = 2; i <= N; ++i)
    {
	    fout << i << ' ' << dad[i] << '\n';
    }
    
    fout.close();
    return 0;
}