#include<fstream>
#include<algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
int n,m,pad[200001],v[400001];
struct tt{
    int x,y,cost;
} muchii[400005];
bool cmp(tt x1, tt x2){
    return x1.cost<x2.cost;
}
long long suma=0;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        pad[i]=-1;
    }
    for(int i=1;i<=m;i++){
        int x,y,c;
        cin>>x>>y>>c;
        //suma+=c;
        muchii[i]={x,y,c};
    }
    sort(muchii+1, muchii+m+1, cmp);
    int cnt=1,k=0;
    while(k<n&&cnt<m){
        int xx=muchii[cnt].x;
        int yy=muchii[cnt].y;
        int x1=xx, y1=yy;
        while(pad[x1]>-1)
            x1=pad[x1];
        while(pad[y1]>-1)
            y1=pad[y1];
        if(x1!=y1){
            v[cnt]=1;
            suma+=muchii[cnt].cost;
            if(x1<y1){
                pad[x1]+=pad[y1];
                pad[y1]=x1;
            }
            else{
                pad[y1]+=pad[x1];
                pad[x1]=y1;
            }
            k++;
        }
        cnt++;
    }
    cout<<suma<<"\n"<<k<<"\n";
    for(int i=1;i<=m;i++){
        if(!v[i])
            cout<<muchii[i].x<<" "<<muchii[i].y<<"\n";
    }
}