#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie
{
    int nod, dist;
} muchNoua;

struct muchie1
{
    int nod1, nod2, dist;
} much1Noua;

int n, m, noduriParc = 1,  dimApm = 0;
vector <muchie1> legatura;
vector< vector < muchie > > leg;
vector <bool> A;

 struct compare
 {
   bool operator()(const muchie1& l, const muchie1& r)
   {
       return l.dist > r.dist;
   }
 };

  priority_queue<muchie1,vector<muchie1>, compare > heap;

void citire()
{
    int a, b, dist1;
    fin>>n>>m;
    leg.resize(n + 1);
    A.resize(n + 1);
    for(int i = 1; i <= n; ++i)
    {
        A[i]= 0;
    }
    A[1] = 1;
    for(int i = 1; i <= m; ++i)
    {
        fin>>a>>b>>dist1;
        muchNoua.dist = dist1;
        muchNoua.nod = b;
        leg[a].push_back(muchNoua);
        muchNoua.nod = a;
        leg[b].push_back(muchNoua);

    }
}

int main()
{
    int i, y;
    citire();
    for(int j = 0; j < leg[1].size(); ++j)
    {
        much1Noua.nod1 = 1;
        much1Noua.nod2 = leg[1][j].nod;
        much1Noua.dist = leg[1][j].dist;
        heap.push(much1Noua);
    }
    while(noduriParc != n)
    {
        much1Noua = heap.top();
        heap.pop();
        if(A[much1Noua.nod2] == 0)
        {
            ++noduriParc;
            dimApm += much1Noua.dist;
            legatura.push_back(much1Noua);
            i = much1Noua.nod2;
            much1Noua.nod1 = i;
            A[i] = 1;
            for(int j = 0; j < leg[i].size(); ++j)
            {
                if(A[leg[i][j].nod] == 0)
                {
                    much1Noua.nod2 = leg[i][j].nod;
                    much1Noua.dist = leg[i][j].dist;
                    heap.push(much1Noua);
                }
            }
        }
    }
    fout<<dimApm<<'\n';
    fout<<legatura.size()<<'\n';
    for(int j = 0; j < legatura.size(); ++j)
    {
        fout<<legatura[j].nod1<<" "<<legatura[j].nod2<<'\n';
    }
}