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

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
vector < pair <int,int> > v[DIM],Arbmin;
vector <int> a(DIM,INF),H(DIM),c(DIM),poz(DIM);
int N,nr,cost_min,M;
void apm(int x){
    std::vector < pair <int , int> >::iterator it;
    for(it=v[x].begin();it!=v[x].end();it++){
        int nod=it->first;
        int cost=it->second;
        a[nod]=min(a[nod],cost);
        if(a[nod]==cost)
            c[nod]=x;
    }
}
void downheap(){
    int p=1,c=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[c],H[p]);
            swap(poz[H[c]],poz[H[p]]);
            p=c;
            c*=2;
        }
        else
            break;
    }
}
void upheap(int L){
    int c=L,p=c/2;
    while(c>1 && a[H[c]]<a[H[p]]){
        swap(H[c],H[p]);
        swap(poz[H[c]],poz[H[p]]);
        c=p;
        p/=2;
    }
}
void hinsert(int x){
    H[++nr]=x;
    poz[x]=nr;
    upheap(nr);
}
int delete_root(){
    int x=H[1];
    swap(H[1],H[nr]);
    swap(poz[H[1]],poz[H[nr]]);
    nr--;
    downheap();
    poz[x]=0;
    return x;
}
int main(){
    fin>>N>>M;
    while(M--){
        int a,b,c;
        fin>>a>>b>>c;
        v[a].push_back(make_pair(b,c));
        v[b].push_back(make_pair(a,c));
    }
    a[1]=0;
    apm(1);
    for(int i=2;i<=N;i++){
        hinsert(i);
    }
    for(int i=1;i<N;i++){
        int x=delete_root();
        apm(x);
        cost_min+=a[x];
        Arbmin.push_back(make_pair(x,c[x]));
        std::vector < pair <int , int> >::iterator it;
        for(it=v[x].begin();it!=v[x].end();it++){
            int nod=it->first;
            if(poz[nod])
                upheap(poz[nod]);
        }
    }
    fout<<cost_min<<"\n"<<N-1<<"\n";
    std::vector < pair <int , int> >::iterator it;
    for(it=Arbmin.begin();it!=Arbmin.end();it++)
        fout<<it->first<<" "<<it->second<<"\n";
    fin.close();fout.close();
    return 0;
}