#include <bits/stdc++.h>

using namespace std;

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


struct Edge{
    int u, v, weight;
    bool operator<(Edge const& other){
        return weight < other.weight;
    }
};

const int NMAX = 200'001;
int n,m;
vector<Edge> edges;

// DSU related
int parent[NMAX];
int level[NMAX];
int apmCost;
vector<Edge> apm;

void make_set(int v){ // initialise the nodes with each unique set
    parent[v] = v;
    level[v] = 0;
}

int find_set(int v){ // finds the representative of a set
    if(v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

void unite(int u, int v){ // unites the sets that have the nodes u and v
    int a = find_set(u); // representative of a
    int b = find_set(v);
    if(a != b){
        if(level[a] < level[b])
            swap(a, b);
        parent[b] = a;
        if(level[a] == level[b])
            ++level[a];
    }
}


void read(){
    fin >> n >> m;
    for(int i = 0; i < m; ++i){
        int a,b,cost;
        fin >> a >> b >> cost;
        Edge e;
        e.u = a;
        e.v = b;
        e.weight = cost;
        edges.push_back(e);
    }
}

void Apm(){
    sort(edges.begin(), edges.end());
    for(int i = 1; i <= n; ++i)
        make_set(i);
    for(auto edge : edges){
        if(find_set(edge.u) != find_set(edge.v)){
            apmCost += edge.weight;
            apm.push_back(edge);
            unite(edge.u, edge.v);
        }
    }
}

void print(){
    fout << apmCost << '\n';
    fout << apm.size() << '\n';
    for(auto it : apm)
        fout << it.u << ' ' << it.v << '\n';
}


int main()
{

    read();
    Apm();
    print();
    return 0;
}