#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
bool visited[200005];
int distances[200005];

struct nod
{
    int fromNode;
    int toNode;
    int toCost;
    bool const operator<(const nod a) const
    {
        if(toCost < a.toCost)
            return false;
        return true;
    }
};


vector<vector<nod> > theNeighbours;
vector<nod> results;
priority_queue<nod> theQueue;

int main()
{
    int n, m;
    fin>>n>>m;
    theNeighbours = vector<vector<nod> > (n + 5);
    for(int i = 0; i < m ; i++)
    {
        int from, to, cost;
        fin>>from>>to>>cost;
        nod a = {.fromNode = from, .toNode = to, .toCost = cost };
        theNeighbours[from].push_back(a);
        int aux = a.fromNode;
        a.fromNode = a.toNode;
        a.toNode = aux;
        theNeighbours[to].push_back(a);
    }
    theQueue.push((nod)
    {
        .fromNode = 0, .toNode = 1, .toCost = 0
    });


    while(!theQueue.empty())
    {

        nod currNode = theQueue.top();

        theQueue.pop();
        if(visited[currNode.toNode] == false)
        {
            for(int i = 0; i < theNeighbours[currNode.toNode].size(); i++)
            {

                int neighbour = theNeighbours[currNode.toNode][i].toNode;
                int cost = theNeighbours[currNode.toNode][i].toCost;
                if(visited[neighbour] == false)
                {
                    nod newEl = {.fromNode = currNode.toNode, .toNode = neighbour, .toCost = cost};
                    theQueue.push(newEl);
                }

            }
            visited[currNode.toNode] = true;
            results.push_back((nod){.fromNode = currNode.fromNode, .toNode = currNode.toNode, .toCost = currNode.toCost});
            distances[currNode.toNode] = currNode.toCost;
        }
        visited[currNode.toNode] = true;


    }
    int sum = 0;
    for(int i = 1; i <= n; i++){
        sum += distances[i];

    }
    fout<<sum<<"\n";
    fout<<results.size() - 1<<"\n";
    for(int i = 1; i < results.size(); i++){
        fout<<results[i].fromNode<<" "<<results[i].toNode<<"\n";
    }

    return 0;
}