#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define NMAX 200005
using namespace std;
ifstream fi("apm.in");
ofstream fo("apm.out");

int N, M;

struct Edge
{
    int nodeOne;
    int nodeTwo;
    int cost;
    bool operator <(const Edge & other) const
    {
        return cost > other.cost;
    }

    Edge(int aNode,int aNode2, int aCost)
    {
        nodeOne = aNode;
        nodeTwo = aNode2;
        cost = aCost;
    }
};

priority_queue<Edge> q;

vector<pair<int,int> > graph[NMAX];

vector<pair<int,int> >  rez;

int totalSum = 0;
int visited[NMAX];

void DoAPrimFlip(int start)
{
    visited[start] = 1;
    for(auto y : graph[start])
        q.push(Edge(start, y.first, y.second));

    for(int i = 1; i <= N-1; ++i)
    {
        while(visited[q.top().nodeTwo] != false)
            q.pop();

        Edge e = q.top();
        totalSum += e.cost;
        visited[e.nodeTwo] = 1;
        rez.push_back({e.nodeOne, e.nodeTwo});

        for(auto y:graph[e.nodeTwo])
        {
            if(visited[y.first] == 0)
                q.push(Edge(e.nodeTwo, y.first, y.second));
        }
    }

}

int main()
{
    fi >> N >> M;
    for(int i = 1; i <= M; ++i)
    {
        int a, b, c;
        fi >> a >> b >> c;
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }

    DoAPrimFlip(1);

    fo << totalSum << "\n";
    fo << N - 1 << "\n";
    for(auto y:rez)
        fo << y.first << " " << y.second << "\n";
}