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

struct DSU {
    vector<int> p, r;
    DSU(int n) : p(n+1), r(n+1,0) { iota(p.begin(), p.end(), 0); }
    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(r[a]<r[b]) swap(a,b);
        p[b]=a;
        if(r[a]==r[b]) r[a]++;
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int N,M; cin>>N>>M;
    struct Edge{int x,y,c;};
    vector<Edge> edges(M);
    for(int i=0;i<M;i++) cin>>edges[i].x>>edges[i].y>>edges[i].c;
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b){ return a.c<b.c; });
    DSU dsu(N);
    long long cost=0;
    vector<pair<int,int>> sol;
    for(auto &e:edges){
        if(dsu.unite(e.x,e.y)){
            cost+=e.c;
            sol.push_back({e.x,e.y});
            if((int)sol.size()==N-1) break;
        }
    }
    cout<<cost<<"\n"<<sol.size()<<"\n";
    for(auto &p:sol) cout<<p.first<<" "<<p.second<<"\n";
    return 0;
}