#include <bits/stdc++.h>

using namespace std;

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

// DSU
vector<int>tata(100005),height(100005);

int get_root(int nod){
    if(nod!=tata[nod]){
        tata[nod]=get_root(tata[nod]);
    }
    return tata[nod];
}

void unite(int x, int y){
    int rx=get_root(x);
    int ry=get_root(y);
    if(height[rx]>height[ry])
        tata[ry]=rx;
    else if(height[rx]<height[ry])
            tata[rx]=ry;
    else{
        tata[ry]=rx;
        height[rx]++;
    }
}

void reset(int n){
    for(int i=1; i<=n; ++i){
        tata[i]=i;
        height[i]=1;
    }

}
//

struct edge{
    int x,y,c;
    edge(int xx=0, int yy=0, int cc=0){
        x=xx;
        y=yy;
        c=cc;
    }

    bool operator<(const edge& other) const{
        return c<other.c;
    }

};

int main()
{
    int n,m;
    f>>n>>m;
    reset(n);
    vector<edge>edges;
    for(int i=1; i<=m; ++i){
        int x,y,c;
        f>>x>>y>>c;
        edges.push_back({x,y,c});
    }
    sort(edges.begin(),edges.end());
    int cost_total=0;
    vector<pair<int,int>>ans;
    for(const auto& [x,y,c] : edges){
        if(get_root(x)==get_root(y))
            continue;
        unite(x,y);
        cost_total+=c;
        ans.push_back({x,y});
    }
    g<<cost_total<<'\n';
    g<<ans.size()<<'\n';
    for(const auto& [x,y] : ans){
        g<<x<<' '<<y<<'\n';
    }


    return 0;
}