#include <fstream>
#define DIM 200005
#define INF 0x3f3f3f3f
#include <vector>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int N,M,nr,Sol;
int x,y,z;
vector <pair <int,int> > v[DIM],ans;
vector <int> a(DIM,INF),H(DIM),poz(DIM),c(DIM);

void apm(int x){
    for(std::vector <pair <int,int> >::iterator it=v[x].begin();it!=v[x].end();it++){
        a[it->first] = min(a[it->first],it->second);
        if(a[it->first] == it->second)
            c[it->first] = x;
    }

}

void up(int x){
    int c=x,p=c/2;

    while(p>=1 && a[H[c]] < a[H[p]]){
        swap(H[c],H[p]);
        swap(poz[H[c]],poz[H[p]]);
        c=p;
        p/=2;
    }

}

void down(int x){
    int p=x,c=p*2;

    while(c<=nr){
        if(c+1<=nr && a[H[c+1]] < a[H[c]])
            c++;
        if(a[H[c]] < a[H[p]]){
            swap(H[p],H[c]);
            swap(poz[H[p]],poz[H[c]]);
            p=c;
            c*=2;
        }
        else
            return;
    }

}

void hinsert(int x){
    H[++nr] = x;
    poz[x]=nr;
    up(nr);
}

int extract(){
    int x = H[1];
    swap(H[1],H[nr]);
    swap(poz[H[1]],poz[H[nr]]);
    nr--;
    poz[x]=0;
    down(1);
    return x;
}

int main(){

    fin >> N >> M;

    while(M--){
        fin >> x >> y >> z;
        v[x].push_back(make_pair(y,z));
        v[y].push_back(make_pair(x,z));
    }

    a[1] = 0;

    apm(1);

    for(int i=2;i<=N;i++)
        hinsert(i);

    while(nr>0){
        int x = extract();
        apm(x);
        Sol+=a[x];
        ans.push_back(make_pair(x,c[x]));
        for(int i=1;i<=N;i++)
            if(poz[x])
                up(poz[x]);
    }

    fout << Sol << "\n";

    fout << N-1 << "\n";

    for(std::vector <pair <int,int> >::iterator it=ans.begin();it!=ans.end();it++)
        fout << it->first << " " << it->second << "\n";

    fin.close();fout.close();

    return 0;

}