#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

#define N 200001

struct edge{
    int from, to, cost;
    edge(int from, int to, int cost):
        from(from), to(to), cost(cost) {}

    bool operator<(const edge &e) const{
        return cost > e.cost;
    }
};

priority_queue<edge> q;
int n, m, viz[N];
vector<edge> sel(N, edge(0, 0, 0));
vector<edge> ve[N];

void addEdges(int x){
    viz[x] = 1;
    for(edge e : ve[x])
        if(viz[e.to] == 0)
            q.push(e);
}

void lazyprims(int s){
    int expected = n-1;
    int edges = 0, totcost = 0;

    addEdges(s);

    while(!q.empty() && edges != expected){
        edge e = q.top();
        q.pop();

        if(viz[e.to] == 1)
            continue;

        sel[++edges] = e;
        totcost += e.cost;
        addEdges(e.to);
    }

    if(edges == expected){
        out << totcost << '\n';
        out << edges << '\n';
        for(int i=1; i<=edges; i++){
            edge e = sel[i];
            out << e.from << ' ' << e.to << '\n';
        }
    }
}


int main(){
    in >> n >> m;
    while(m--){
        int x, y, c;
        in >> x >> y >> c;
        ve[x].push_back(edge(x,y,c));
        ve[y].push_back(edge(y,x,c));
    }

    lazyprims(1);
}