#include <bits/stdc++.h>
#include <fstream>
using namespace std;

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

const int INTMAX = 2147483646;
vector<vector<pair<int,int>>>Edges;
vector<pair<int,int>> edgesfinal;

int father[200001];
vector<int>mstSet;

int main()
{
    int keyValues[200001];
    for(int i=1; i<=200001; i++)
        keyValues[i]=INTMAX;
    int nrNodes,nrEdges,node1,node2,weight;

    f>>nrNodes>>nrEdges;

    for(int i=0; i<=nrNodes; i++)
        Edges.push_back(vector<pair<int,int>>());

    for(int i=1; i<=nrEdges; i++)
    {
        f>>node1>>node2>>weight;
        Edges[node1].push_back(make_pair(node2,weight));
        Edges[node2].push_back(make_pair(node1,weight));

    }

    keyValues[1]=0;
    int currentNode = 1, currentMinWeight, nextNode,s=0;
    do
    {
        mstSet.push_back(currentNode);
        for(int i=0; i<Edges[currentNode].size(); i++)
        {
            int tupleFirst = Edges[currentNode][i].first;
            int tupleSecond = Edges[currentNode][i].second;
            if(tupleSecond < keyValues[tupleFirst])
            {
                father[tupleFirst]=currentNode;
                keyValues[tupleFirst] = tupleSecond;
            }
        }
        currentMinWeight=INTMAX;
        for(int i=1; i<=nrNodes; i++)
        {
            auto it = find(mstSet.begin(),mstSet.end(),i);
            if(keyValues[i]<currentMinWeight && it == mstSet.end()) ///daca e mai mic decat minimul curent si nu e in minimal spanning tree
            {
                nextNode = i;
                currentMinWeight = keyValues[i];
            }
        }

        currentNode = nextNode;
        s+=currentMinWeight;
        edgesfinal.push_back(make_pair(currentNode, father[currentNode]));
    }
    while(mstSet.size()<nrNodes-1);
    g<<s<<endl;
    g<<edgesfinal.size()<<endl;

    for(int i=0; i<edgesfinal.size(); i++)
        g<<edgesfinal[i].first<<' '<<edgesfinal[i].second<<'\n';
    return 0;
}