#include<fstream>
#include<algorithm>
#include<vector>
#define pb push_back

using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
const int maxn = 400100;
struct muchie {int e1,e2,cost;};
muchie G[maxn];
int A[maxn],c[maxn];
int n,m;
void initializare(){
    int i;
    cin >> n >> m;
    for(i = 1;i <= m;i++){
        cin >> G[i].e1 >> G[i].e2 >> G[i].cost;
    }
    for(i = 1;i <= n;i++)
        c[i] = i;
}
void Afisare(){
    int i,costAPM = 0;
    for(i = 1;i < n;i++){
        costAPM += G[A[i]].cost;
    }
    cout << costAPM << "\n";
    cout << n - 1<< "\n";
    for(i = 1;i < n;i++){
        cout << G[A[i]].e1 << " " << G[A[i]].e2 << "\n";
    }
}
bool cmp(muchie a,muchie b){
    return (a.cost < b.cost);
}
void SortareMuchii(){
    sort(G + 1,G + m + 1,cmp);
}
int main()
{
    int i,j,minim,maxim,NrmSEL;
    ios_base::sync_with_stdio();
    cin.tie(0);
    initializare();
    SortareMuchii();
    NrmSEL = 0;///numarul de muchii selectate
    for(i = 1;NrmSEL < n-1;i++){
        if(c[G[i].e1] != c[G[i].e2]){
            ///Nu formeaza cicluri
            A[++NrmSEL] = i;
            maxim = max(c[G[i].e2],c[G[i].e1]);
            minim = min(c[G[i].e2],c[G[i].e1]);
            for(j = 1;j <= n;j++)
                if(c[j] == maxim) c[j] = minim;
        }
    }
    Afisare();
	return 0;
}