#include <bits/stdc++.h>
using namespace std;
#define N 400001
#define f first
#define s second
ifstream in("apm.in");
ofstream out("apm.out");
struct graf{
    int c;
    int x;
    int y;
} G[N];
int L[N];
pair<int,int> r[N];
bool comp(graf& i, graf& j){
    return (i.c<j.c);
}
int main(){
    int n,m,i,a,b,d,j;
    in>>n>>m;
    for(i=1; i<=m; ++i){
        in>>a>>b>>d;
        G[i].c=d;
        G[i].x=a;
        G[i].y=b;
    }
    sort(G+1, G+m+1, comp);
    for(i=1; i<=n; ++i)
        L[i]=i;
    i=1;
    int ct=0;
    int k=0;
    while(k<n-1){
        if(L[G[i].x]!=L[G[i].y]){
            r[++k]=make_pair(G[i].x, G[i].y);
            ct+=G[i].c;
            for(j=1; j<=n; ++j)
                if(L[j]==L[G[i].x]) L[j]=L[G[i].y];
        }
        ++i;
    }
    out<<ct<<"\n"<<k<<"\n";
    for(i=1; i<=k; ++i)
        out<<r[i].f<<" "<<r[i].s<<"\n";
    return 0;
}