#include <bits/stdc++.h>

using namespace std;

int n,m,a,b,c,t[200005],fs,hs,tot;
struct drum{
    int x, y, z;
};
drum mnm={0,0,99999};
vector <pair<int,int>> p[200005];
pair<int,int> f[200005];
drum h[200005];
int v[200005];

void up(int pos){
    if(pos==1) return;
    if(h[pos].z>=h[pos/2].z) return;
    swap(h[pos],h[pos/2]);
    up(pos/2);
}

void down(int pos){
    if(2*pos>hs) return;
    if(2*pos==hs){
        if(h[2*pos].z<h[pos].z) swap(h[2*pos],h[pos]);
        return;
    }
    if(h[2*pos].z>=h[pos].z && h[2*pos+1].z>=h[pos].z) return;
    int fiu;
    if(h[2*pos].z>h[2*pos+1].z) fiu=2*pos+1;
    else fiu=2*pos;
    swap(h[pos], h[fiu]);
    down(fiu);
}

void del(int pos){
    if(pos==hs){
        hs--;
        return;
    }
    swap(h[pos],h[hs]);
    hs--;
    if(pos!=1 && h[pos].z<h[pos/2].z) up(pos);
    else down(pos);
}

int main()
{
    ifstream in("apm.in");
    ofstream out("apm.out");
    in >> n >> m;
    for(int i=1;i<=m;i++){
        in >> a >> b >> c;
        p[a].push_back({b,c});
        p[b].push_back({a,c});
        if(c<mnm.z){
            mnm={a,b,c};
        }
    }
    hs=1;
    h[1]=mnm;
    while(hs){
        mnm=h[1];
        del(1);
        if(!v[mnm.x] || !v[mnm.y]){
            tot+=mnm.z;
            for(int i=0;i<p[mnm.x].size();i++){
                if(!v[p[mnm.x][i].first]){
                    h[++hs]={mnm.x,p[mnm.x][i].first,p[mnm.x][i].second};
                    up(hs);
                }
            }
            for(int i=0;i<p[mnm.y].size();i++){
                if(!v[p[mnm.y][i].first]){
                    h[++hs]={mnm.y,p[mnm.y][i].first,p[mnm.y][i].second};
                    up(hs);
                }
            }
            f[++fs]={mnm.x,mnm.y};
        }
        v[mnm.x]=1;
        v[mnm.y]=1;
    }
    out << tot << '\n' << fs << '\n';
    for(int i=1;i<=fs;i++) out << f[i].first << ' ' << f[i].second << '\n';
}