#include <bits/stdc++.h>
#define FastIo() ios_base::sync_with_stdio(false), fin.tie(nullptr),fout.tie(nullptr);
#define ll long long 
#define pii pair<int,int>
#define pipii pair<int,pair<int,int>>
using namespace std;

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

//#define fin cin
//#define fout cout

struct DSU{
    vector<int> t;

    DSU(int _n) {
        t.resize(_n + 1);
        for(int i=1;i<=_n;i++) t[i]=i;
    }

    int get_root(int x){
        if(t[x] != x) return t[x] = get_root(t[x]);
        return x;
    }
    bool join(int x, int y) {
        x = get_root(x);
        y = get_root(y);

        if (x == y) return false;

        t[x]=y;
        return true;
    }
    bool same_union(int x, int y){
        return (get_root(x) == get_root(y));
    }
};

int n, m;
int w, x, y;
int main(){
    fin>>n>>m;
    DSU dsu = DSU(n);

    vector<pair<int,pair<int,int>>> edges;
    vector<pair<int,int>> apm_edges;
    for(int i=1;i<=m;i++){
        fin>>x>>y>>w;
        edges.push_back({w,{x,y}});
    }
    sort(edges.begin(),edges.end());
    ll minimum_cost = 0;
    for(int i=0;i<m;i++){
        x = edges[i].second.first;
        y = edges[i].second.second;
        if(dsu.join(x,y)){
            minimum_cost+=edges[i].first;
            apm_edges.push_back({x,y});
        }
    }
    fout<<minimum_cost<<'\n'<<n-1<<'\n';
    for(int i=0;i<n-1;i++)
        fout<<apm_edges[i].first<<' '<<apm_edges[i].second<<'\n';

    return 0;
}