#include <bits/stdc++.h>
#define Dim 200001
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

struct muchie
{
   int vertex,cost;
};

struct pereche
{
    int a,b,c;
};

struct cmp
{
    bool operator ()(pereche X,pereche Y)
    {
        if(X.c >= Y.c ) return 1;
        else return 0;
    }
};

vector < muchie > V[Dim];
priority_queue < pereche, vector <pereche> , cmp > minheap;

int N,M,x,y,c,cnt,cost_t,there_A[Dim],ancient[Dim];

int main()
{

    f>>N>>M;
    for(int i=1;i<=M;i++)
    {
        f>>x>>y>>c;
        V[x].push_back({y,c});
        V[y].push_back({x,c});
    }

    for(unsigned int i=0;i<V[1].size();i++)
    {
        x=V[1][i].vertex;
        y=V[1][i].cost;
        minheap.push( { 1 , x , y } );
    }

    there_A[1]=1;
    while(cnt<N-1)
    {
        int nod1,nod2,nodc;
        bool stop=0;
        while(!minheap.empty() && stop==0 )
        {
            pereche v=minheap.top();
            minheap.pop();
            nod1=v.a; nod2=v.b; nodc=v.c;
            if( !there_A[nod2] )
            {
                there_A[nod2]=1;
                ancient[nod2]=nod1;
                cost_t+=nodc;
                cnt++;
                stop=1;
            }
        }

        for(unsigned int i=0;i<V[nod2].size();i++)
        {
            int vecin=V[nod2][i].vertex,vecinc=V[nod2][i].cost;
            if( !there_A[vecin] )
            minheap.push({nod2,vecin,vecinc});

        }

    }

    g<<cost_t<<'\n'<<cnt<<'\n';
    for(int i=1;i<=N;i++)
    if( ancient[i] ) g<<ancient[i]<<" "<<i<<'\n';


    return 0;
}