#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int INF = 1e9;

int n,m,x,y,c,costTotal = 0;
vector<int> dist;
vector<vector<pair<int,int>>> adj;
vector<int> visited;
vector<pair<int,int>> muchiiAPM;

void prim(){
    vector<int> tata(n+1, 0);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push({0,1});

    dist[1] = 0;

    while(!pq.empty()){
        auto [cost,nod] = pq.top();
        pq.pop();

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

        visited[nod] = 1;
        costTotal += cost;
        for(auto& [neigh, wt]: adj[nod]){
            if(visited[neigh] == 0 && dist[neigh] > wt){
                tata[neigh] = nod;
                dist[neigh] = wt;
                pq.push({wt, neigh});
            }
        }

    }

    g << costTotal << '\n';
    g << n-1 << '\n';

    for(int i=1; i<=n; i++){
        if(tata[i] != 0){
            g << tata[i] << " " << i << '\n';
        }
    }


}

int main(){

    f >> n >> m;
    dist.resize(n+1, INF);
    visited.resize(n+1, 0);
    adj.resize(n+1, vector<pair<int,int>>());
    for(int i=1; i<=m; i++){
        f >> x >> y >> c;
        adj[x].push_back({y,c});
        adj[y].push_back({x,c});
    }
    prim();


    return 0;
}