#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 1000005;

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 cost_total = 0;

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

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

         viz[u]=true;
         cost_total+=d[u];

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

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

    // construim vectorul de muchii ale APM
    for (int i=1;i<=n;i++)
        if (tata[i]!=0)
            apm.push_back({i, tata[i]});

    return cost_total;
}


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

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

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