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

using namespace std;

#define NMAX 200005
#define MMAX 800005
#define INF 130000000

//int dist[NMAX];

int vizitat[NMAX];

vector<int> cost[NMAX];

vector<int> graph[NMAX];

vector< pair<int, int> > muchii;

priority_queue< pair<int, pair<int, int> > > heap;

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

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

    /*for(int i = 1; i <= N; i++)
    {
        //dist[i] = INF;
        heap.push(make_pair((-1)*cost[i], i));
    }*/

    for(unsigned int i = 0; i < graph[1].size(); i++)
    heap.push( make_pair( (-1)*cost[1][i], make_pair(1, graph[1][i]) ) );//Bagam muchiile vecine nodului 1
    vizitat[1] = 1;
    //dist[1] = 0;

    //heap.push(make_pair((-1)*dist[1], 1));

    int answer = 0;

    while(!heap.empty())
    {
        int plec = -1;
        int dest = -1;
        pair<int, int> muchie;
        int costM;
        pair<int, pair<int, int> > p = heap.top();

        costM = -p.first;
        muchie = p.second;

        plec = muchie.first;
        dest = muchie.second;
        heap.pop();

        //if(dist[index] == p.first*(-1))
        if(vizitat[plec] && vizitat[dest]) continue; //ambele vititate -> skip
        else if(!vizitat[dest]) //una vizitata
        {
            vizitat[plec] = 1;
            vizitat[dest] = 1;

            int lim = graph[dest].size();
            for(int t = 0; t < lim; t++)
            {
                int vecin = graph[dest][t];
                int cost2 = cost[dest][t];
                heap.push( make_pair( (-1)*cost2, make_pair(dest, vecin) ) );//Bagam muchiile vecine nodului destinatie
            }

            muchii.push_back( make_pair(plec, dest) );
            answer += costM;
        }
    }

    g<<answer<<endl;
    g<<muchii.size()<<endl;
    for(unsigned int i = 0; i < muchii.size(); i++)
    {
        g<<muchii[i].first<<" "<<muchii[i].second<<endl;
    }

    return 0;
}