//Prim

#include <bits/stdc++.h>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
vector<pair<int,int>> adj[200001];
int viz[200001];
vector<pair<int,int>> muchii;


int main() {

    int n,m;
    fin>>n>>m;

    int x,y,c;
    for (int i=1;i<=m;i++) {
        fin>>x>>y>>c;
        adj[x].push_back({y,c});
        adj[y].push_back({x,c});
    }

    for (int i=1;i<=n;i++) {viz[i]=0;}

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

    pq.push({0,1,-1});
    long long totalCost = 0;

    while (pq.size()>0) {
        auto [cost, nod, par] = pq.top();
        pq.pop();

        if (viz[nod]==1) continue;

        viz[nod]=1;
        totalCost+=cost;

        if (par!=-1) muchii.push_back({par,nod});

        for (auto [vecin,pondere]:adj[nod]) {
            if (viz[vecin]==0) {
                pq.push({pondere,vecin,nod});
            }
        }
    }

    fout<<totalCost<<"\n";
    fout<<muchii.size()<<"\n";
    for (auto [u,v] : muchii) {
        fout<<u<<" "<< v<< "\n";
    }

}