#include<fstream>
#include<list>
#include<bitset>
#include<queue>
#include<climits>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int NMAX = 200005, INF = INT_MAX, MMAX = 400005;

struct edge{

    int cost, firstNode, secondNode;
};

struct graphStructure{

    int nextNode, cost;
};

list<graphStructure> graph[NMAX];
int nodesCount, edgesCount;

inline void read_data(){

    fin >> nodesCount >> edgesCount;

    int from, to, cost;
    while(edgesCount--){

        fin >> from >> to >> cost;
        graph[from].push_back({to, cost});
        graph[to].push_back({from, cost});
    }
}

class compare{

    bool ok;
    public:
        bool operator ()(const edge &a, const edge &b)const{
            if(ok) return a.cost < b.cost;
            return a.cost > b.cost;
        }

};

pair< int , int > MSTEdges[MMAX];

inline int getMST(){

    int distances[NMAX];
    fill(distances + 2, distances + 1 + nodesCount, INF);
    distances[1] = 0;

    bitset<NMAX> visited;
    priority_queue<edge, vector<edge> , compare > heapForPrim;
    heapForPrim.push({0, 1, 1});


    list<graphStructure>::iterator it;
    int node1, node2, currentEdgeCost, MSTCost = 0;

    while(!heapForPrim.empty()){

        node1 = heapForPrim.top().secondNode;
        node2 = heapForPrim.top().firstNode;
        currentEdgeCost = heapForPrim.top().cost;
        heapForPrim.pop();

        if(!visited[node1] and distances[node1] >= currentEdgeCost){

            visited[node1] = true;
            distances[node1] = currentEdgeCost;
            MSTCost += currentEdgeCost;
            MSTEdges[++edgesCount] = {node1, node2};

            for(it = graph[node1].begin(); it != graph[node1].end(); ++it)
                if(!visited[ it -> nextNode ] and distances[ it -> nextNode ] > it -> cost){

                    distances[ it -> nextNode ] = it -> cost;
                    heapForPrim.push({it -> cost, node1, it -> nextNode});
                }
        }
    }

    return MSTCost;
}

inline void printMST(){

    int Iterator;
    for(Iterator = 1; Iterator <= edgesCount; ++Iterator)
        fout << MSTEdges[Iterator].first << ' ' << MSTEdges[Iterator].second << '\n';

}

int main(){

    read_data();
    fout << getMST() << '\n' << nodesCount - 1 << '\n';
    printMST();
}