#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;

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

struct Edge { 
    int u,v;
    long long w; 
};

struct DSU {
    vector<int> p, s;
    DSU(int n=0){ 
        p.resize(n+1); 
        s.assign(n+1,1); 
        for(int i=1;i<=n;i++) 
            p[i]=i; 
    }
    int find(int x){ 
        return p[x]==x?x:p[x]=find(p[x]); 
    }
    bool unite(int a,int b){ 
        a=find(a); b=find(b); 
        if(a==b) return false; 
        if(s[a]<s[b]) swap(a,b); 
        p[b]=a; s[a]+=s[b]; return true; 
    }
};

int main(){
    int n,m,u,v; 
    long long w; 
    fin>>n>>m;
    vector<Edge> edges; edges.reserve(m);
    for(int i=0;i<m;i++){ 
        fin>>u>>v>>w; 
        edges.push_back({u,v,w}); 
    }
    sort(edges.begin(), edges.end(), [](const Edge&a,const Edge&b){ 
        return a.w<b.w; 
    });
    DSU dsu(n);
    long long total=0;
    vector<Edge> mst;
    for(auto &e: edges){
        if(dsu.unite(e.u,e.v)){
            mst.push_back(e);
            total += e.w;
            if((int)mst.size() == n-1) break;
        }
    }
    fout << total << '\n';
    fout << mst.size() << '\n';
    for(auto &e: mst) fout << e.u << ' ' << e.v << '\n';
    return 0;
}