#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define MMAX 400000
#define NMAX 200000
using namespace std;
ifstream fi("apm.in");
ofstream fo("apm.out");
int N, M;

struct Edge{
    int initial, secondary, cost;
} edges[MMAX];

bool cmp(Edge first, Edge second)
{
    return (first.cost < second.cost);
}
int parent[NMAX];

vector<Edge> selectedEdges;

int main()
{
    fi >> N >> M;
    for(int i = 1; i <= M; ++i)
        fi >> edges[i].initial >> edges[i].secondary >> edges[i].cost;

    sort(edges + 1, edges + M + 1, cmp);

    for(int i = 1; i <= N; ++i)
        parent[i] = i;

    for(int i = 1; selectedEdges.size() <= N-1 && i <= M; ++i)
    {
        if(parent[edges[i].initial] != parent[edges[i].secondary])
        {
            selectedEdges.push_back(edges[i]);

            int minimal = min(parent[edges[i].initial], parent[edges[i].secondary]);
            int maximal = max(parent[edges[i].initial], parent[edges[i].secondary]);

            for(int j = 1; j <= N; ++j)
                if(parent[j] == maximal)
                    parent[j] = minimal;
        }
    }
    long long sum = 0;
    for(auto y:selectedEdges)
        sum += y.cost;

    fo<<sum<<"\n"<<selectedEdges.size()<<"\n";

    for(auto y:selectedEdges)
        fo<<y.secondary<<" "<<y.initial<<"\n";
}