#include<cstdio>
#include<vector>
#include<algorithm>
const int NMAX = 200000;
struct edge{
int from , to;
int cost;
bool operator <(const edge &other){
    return cost < other.cost;
}
};
std::vector< std::pair<int , int> > Sol;
std::vector<edge> Edges;
int father[NMAX + 1];
int getFather(int x){
    while(father[x] != x)
        x = father[x];
    return x;
}
void join(int x , int y){
    int val = getFather(y);
    father[val] = getFather(x);
}
int main()
{
    freopen("apm.in" ,"r",stdin);
    freopen("apm.out" ,"w",stdout);
    int n , m;
    scanf("%d%d" , &n , &m);
    for(int i = 1; i <= m ; i ++)
    {
        int x, y, cost;
        scanf("%d%d%d", &x, &y, &cost);
        Edges.push_back({x, y, cost});

    }
    std:: sort(Edges.begin(), Edges.end());
    for(int i = 1; i <= n ; i ++)
    {
        father[i] = i;
    }
    long long totalCost = 0;
    for(int i = 0; i < m ; i ++){
        int x = Edges[i].from;
        int y = Edges[i].to;

        if(getFather(x) != getFather(y)){
            join(x , y);
            totalCost += Edges[i].cost;
            Sol.push_back({x , y});
        }
    }
    printf("%lld\n" , totalCost);
    printf("%d\n" , Sol.size());
    for(auto x : Sol){
        printf("%d %d\n", x.first, x.second);
    }
}