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

ifstream fin("kruskal.in");
ofstream fout("kruskal.out");

typedef vector<int> vi;
// vector<vector<pair<int,int>>> g;
vector<tuple<int,int,int>> edges;
// vector<vector<int>> apm;
int n, m;
vi link(n+1,0);

int find(int x){
    while(x!=link[x])
        x=link[x];
    return x;
}

void unite(int x, int y){
    x=find(x), y=find(y);
    link[x]=y;
}

void kruscal(){
    sort(edges.begin(),edges.end());
    int cost=0;
    for(int i=1;i<=n;++i)
        link[i]=i;
    // for(int i=1;i<=n;++i) size[i]=1;
    for(auto &t:edges){
        int x,y,c;
        tie(c,x,y)=t;
        if(find(x)!=find(y)) unite(x, y), cost+=c;
    }

    // vector<int> arb(n+1,-1); // fathers
    fout<<cost<<"\n";
    for(int i=1;i<=n;++i)
        if(link[i]!=i) fout<<i<<" "<<link[i]<<"\n";
}

int main(){
    fin>>n>>m;
    link.resize(n+1,-1);
    for(int i=m;i--;){
        int x,y,c;
        fin>>x>>y>>c;
        // g[x].push_back({c,y});
        // g[y].push_back({c,x});
        edges.push_back(make_tuple(c,x,y));
    } // cit
    kruscal();
}