#include <iostream>
#include <vector>
#include <bits/stdc++.h>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");
vector<int>Color;
struct Muchie{
    int u,v,c;
};

bool ordine(Muchie a, Muchie b){
    return a.c<b.c;
}

vector<Muchie>G;
vector<Muchie>G2;

int main(){


    int n,m,x,y,z,i,u,v,cost=0,nr=0,q;
    f>>n>>m;
    Color.resize(n);
    for(i=1;i<=n;i++){
        Color[i]=i;
    }

    while(f){
        f>>x>>y>>z;
        G.push_back({x,y,z});
    }
    sort(G.begin(), G.end(), ordine);

    for(i=0;i<m;i++){
        u=G[i].u;
        v=G[i].v;
        if(Color[u] != Color[v]){
            cost += G[i].c;
            nr++;
            G2.push_back(G[i]);
            q=Color[v];
            for(int k=1;k<=n;k++){
                if(Color[k]==q){
                    Color[k]=Color[u];
                }
            }
        }
    }
    g<<cost<<"\n"<<nr<<"\n";
    for(i=0;i<nr;i++){
        g<<G2[i].u<<" "<<G2[i].v<<"\n";
    }
    return 0;
}