#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=200000,M=400000;

class Edge{
    public:
        int v1,v2;
        int c;
        Edge(){
        }
        Edge(int vv1,int vv2,int cc){
            v1=vv1;
            v2=vv2;
            c=cc;
        }
        bool operator<(const Edge&e)const{
            return c<e.c;
        }
};

Edge e[M+1];
Edge tree[N+1];
int father[N+1];
int n,m;
int root(int x){
    if(father[x]==0)
        return x;
    father[x]=root(father[x]);
    return father[x];
}
int best_cost;
void setApm(){
    int x=0;
    sort(e+1,e+m+1);
    for(int i=1;i<=m;i++){
        int r1=root(e[i].v1);
        int r2=root(e[i].v2);
        if(r1!=r2){
            father[r1]=r2;
            tree[++x]=e[i];
            best_cost+=e[i].c;
        }
    }
}
int main(){
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        int z;
        scanf("%d%d%d",&x,&y,&z);
        e[i]=Edge(x,y,z);
    }
    setApm();
    //setAncestors();
    printf("%d\n%d\n",best_cost,n-1);
    for(int i=1;i<n;i++)
        printf("%d %d\n",tree[i].v1,tree[i].v2);
    return 0;
}