#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

const int NMAX = 200000;

struct edge{
    int u, v, w;
    edge(int u = 0, int v = 0, int w = 0): u(u), v(v), w(w){}
};

vector<edge> edges;
vector<int> G[NMAX + 5], T[NMAX + 5], viz;

class Compare{
public:
    bool operator() (int a, int b){
        return edges[a].w > edges[b].w;
    }
};

priority_queue <int, vector<int>, Compare> pq;

int main(){
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    int n, m, k, u, v, w, total_w;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i ++){
        scanf("%d%d%d", &u, &v, &w);
        edges.push_back(edge(u, v, w));
        G[u].push_back(i);
        G[v].push_back(i);
    }

    int start = 1;
    viz = vector<int>(n + 1, 0);
    viz[start] = 1;
    for(const auto edge_id: G[start])
        pq.push(edge_id);


    vector<int> sol;
    total_w = 0;
    while(!pq.empty()){
        int edge_id = pq.top();
        pq.pop();
        u = edges[edge_id].u;
        v = edges[edge_id].v;
        w = edges[edge_id].w;
        
        if(viz[u] && viz[v])
            continue;
        if(viz[v])
            swap(u, v);
        viz[v] = 1;
        total_w += w;
        sol.push_back(edge_id);

        T[u].push_back(edge_id);
        T[v].push_back(edge_id);


        for(const auto new_edge_id: G[v])
            if(!viz[edges[new_edge_id].u] || !viz[edges[new_edge_id].v])
                pq.push(new_edge_id);
    }

    printf("%d\n%d\n", total_w, n - 1);
    for(const auto edge_id: sol)
        printf("%d %d\n", edges[edge_id].u, edges[edge_id].v);
    return 0;
}