#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <fstream>

using namespace std;

struct comparator
{
bool operator()( int i , int j)
    {
    return i > j;
    }
};

priority_queue<int,vector<int>, comparator > heap ;

const int MAXN = 200200;
const int INF = 200000200;

int VEC[MAXN] , ANS , V[MAXN] ,POZ[MAXN];
vector <pair<int,int> > VECT[MAXN] , VANS;
int N,M,L,C[MAXN];

void introduce_in_apm(int x)
{
    for (int i=0 ; i<VECT[x].size() ; i++)
    {
        int nod = VECT[x][i].first;
        int cost = VECT[x][i].second;
        V[nod] = min(V[nod],cost);
        if (V[nod] == cost) VEC[nod] = x;
    }
}


int main()
{
    ifstream f("apm.in") ;
    ofstream g("apm.out") ;

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

    for(int i = 1;i <= N; ++i) V[i] = INF;
    V[1] = 0;
    introduce_in_apm(1);
    for(int i = 2;i <= N; ++i)
    {
        heap.push(i) ;
    }
    for(int i = 1;i < N; ++i)
    {
        int x = heap.top() ;
        heap.pop() ;
        introduce_in_apm(x);
        ANS += V[x];
        VANS.push_back(make_pair(x,VEC[x]));
        for (int j = 0;j < VECT[x].size(); j++)
        {
            int nod = VECT[x][j].first;
            if (POZ[nod]) heap.pop() ;
        }
    }
    g<<ANS<<"\n" ;
    g<<N-1<<"\n" ;
    for (int i=0 ; i<N-1 ; i++) g<<VANS[i].first<<" "<<VANS[i].second<<"\n" ;
    f.close() ;
    g.close() ;
    return 0;
}