#include <bits/stdc++.h>
#define N 200001
#define M 1001
#define f first
#define s second
using namespace std;
int nr=0, n, m,k=0;
long long S=0;
pair<int,int> a[N*4];
pair<int,pair<int,int> > h[N*4];
int b[4*N], c[N];
pair<int,int> r[N];
bool v[N];
void apm(){
    int i,j,z,o=1,p;
    while(k!=n){
        i=h[0].s.f;
        p=h[0].s.s;
        z=-h[0].f;
        h[0].f=-M;
        pop_heap(h, h+o);
        if(!v[i]){
            v[i]=1;
            S+=z*1LL;
            r[++k]={p,i};
            j=c[i];
            while(j){
                if(!v[a[j].f]){
                    h[o].s.f=a[j].f;
                    h[o].s.s=i;
                    h[o++].f=-a[j].s;
                    push_heap(h,h+o);
                }
                j=b[j];
            }
        }
    }
}
void add(int x,int y,int z){
    a[++nr].f=y;
    a[nr].s=z;
    b[nr]=c[x];
    c[x]=nr;
}
int main(){
    int i,x,y,z;
    cin>>n>>m;
    for(i=1; i<=m; ++i){
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z);
    }
    h[0].s.f=1;
    apm();
    cout<<S<<"\n"<<n-1<<"\n";
    for(i=2; i<=n; ++i)
        cout<<r[i].f<<" "<<r[i].s<<"\n";
    return 0;
}