#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 200005;

vector <pair<int,int>> G[NMAX];

int n,m;

long long Prim (int start, vector<pair<int, int>> &apm){

    priority_queue < pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>> > pq;

    vector <int> d(n+1, 1e9);
    vector <int> tata(n+1, 0);
    vector <bool> viz(n+1, false);

    d[start]=0;
    pq.push({0, start});

    long long ctot=0;

    while (!pq.empty()){
        int u=pq.top().second;
        int cost=pq.top().first;

        pq.pop();

        if (viz[u]==true) continue;

        viz[u]=true;
        ctot+=cost;

        for (auto vecin : G[u]){
            int v=vecin.first;
            int c=vecin.second;

            if (viz[v]==false && c < d[v]){
                d[v]=c;
                tata[v]=u;
                pq.push(make_pair(d[v], v));
            }
        }
    }

    for (int i=1;i<=n;i++)
        if (tata[i]!=0)
            apm.push_back({i, tata[i]});

    return ctot;
}

int main(){
    f>>n>>m;
    for (int i=1;i<=m;i++){
        int nod1, nod2, cost;
        f>>nod1>>nod2>>cost;
        G[nod1].push_back({nod2, cost});
        G[nod2].push_back({nod1, cost});
    }

    vector <pair<int,int>> apm;
    long long sol = Prim(1,apm);

    g<<sol<<'\n';
    g<<apm.size()<<'\n';
    for (auto nod : apm){
        g<<nod.first<<" "<<nod.second<<'\n';
    }
}