#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 root[NMAX];

vector<Edge> selectedEdges;

int Father(int node)
{
    if(root[node] == node)
        return node;

    root[node] = Father(root[node]);
    return root[node];
}

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)
        root[i] = i;

    for(int i = 1; selectedEdges.size() <= N-1 && i <= M; ++i)
    {
        int rootInitial = Father(edges[i].initial);
        int rootSecondary = Father(edges[i].secondary);
        if(rootInitial != rootSecondary)
        {
            selectedEdges.push_back(edges[i]);
            root[rootSecondary] = rootInitial;
        }
    }
    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";
}