#include <bits/stdc++.h>

#define Nmax 200005
#define Mmax 400005

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

pair < int, int > Graph[Nmax];

struct Edge
{
    int home, destination, cost;
};

Edge Edges[Mmax];

int Father[Nmax];
int Rank[Nmax];

int N, M;

int length, cost;

bool compareEdges(Edge A, Edge B)
{
    return A.cost < B.cost;
}

int findNode(int node)
{
    while(Father[node] != node)
        node = Father[node];
    return node;
}

void unionNodes(int first, int second)
{
    if(Rank[first] < Rank[second])
        Father[first] = second;
    if(Rank[second] < Rank[first])
        Father[second] = first;
    if(Rank[first] == Rank[second])
    {
        Father[second] = first;
        ++Rank[first];
    }
}

int main()
{
    fin >> N >> M;
    for(int i = 1; i <= M; ++i)
        fin >> Edges[i].home >> Edges[i].destination >> Edges[i].cost;
    sort(Edges + 1, Edges + M + 1, compareEdges);
    for(int i = 1; i <= N; ++i)
        Father[i] = i;
    for(int i = 1; i <= N; ++i)
        Rank[i] = 1;
    for(int i = 1; i <= M; ++i)
    {
        int home = findNode(Edges[i].home);
        int destination = findNode(Edges[i].destination);
        if(home != destination)
        {
            unionNodes(home, destination);
            ++length;
            Graph[length].first = Edges[i].home;
            Graph[length].second = Edges[i].destination;
            cost += Edges[i].cost;
        }
    }
    fout << cost << "\n" << length << "\n";
    for(int i = 1; i <= length; ++i)
        fout << Graph[i].second << " " << Graph[i].first << "\n";
    return 0;
}