#include <bits/stdc++.h>
#define mod 1000000007

using namespace std;

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

struct edge{
    int x,y,c;

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

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

vector<int>tata(200005),height(200005);
vector<edge>edges;
vector<pair<int,int>>ed_ans;
int parinte(int nod){
    int cp_node=nod;
    while(nod!=tata[nod])
        nod=tata[nod];


    while(cp_node != nod){
        int tx=tata[cp_node];
        tata[cp_node]=nod;
        cp_node=tx;
    }
    return nod;
}
void unite(int x, int y){
    int px=parinte(x);
    int py=parinte(y);

    if(height[px]<height[py])
            tata[px]=py;
    else if(height[px]>height[py])
            tata[py]=px;
        else{
            tata[py]=px;
            height[px]+=1;
            }
}

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

    int n,m;
    f>>n>>m;
    reset(n);
    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=0,cnt=0;
    for(const auto&[x,y,c]:edges){
        if(parinte(x)==parinte(y))
            continue;
        unite(x,y);
        ed_ans.push_back({x,y});
        cost+=c;
        ++cnt;
        if(cnt>n-1)
            break;
    }
    g<<cost<<'\n';
    g<<ed_ans.size()<<'\n';
    for(const auto& [x,y] : ed_ans)
        g<<x<<' '<<y<<'\n';


    return 0;

}