#include <fstream>

using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

const int  INF = 1e9;

int vf[800005],urm[800005],lst[800005],nh,h[200005],poz[200005],nr,d[200005],cst[800005],m,n,x,y,c,cost,pred[200005];

void adauga1(int x, int y, int c){
    vf[++nr]=y;
    urm[nr]=lst[x];
    cst[nr]=c;
    lst[x]=nr;
}
void schimb(int p, int q)
{
    swap(h[p],h[q]);
    poz[h[p]]=p;
    poz[h[q]]=q;
}
void urca(int p)
{
    while(p>1&&d[h[p]]<d[h[p/2]])
    {
        schimb(p,p/2);
        p/=2;
    }
}
void adauga(int p)
{
    h[++nh]=p;
    poz[p]=nh;
    urca(nh);
}
void coboara(int p)
{
    int fs=2*p, fd=2*p+1, bun=p;
    if(fs<=nh&&d[h[fs]]<d[h[bun]])
    {
        bun=fs;
    }
    if(fd<=nh&&d[h[fd]]<d[h[bun]])
    {
        bun=fd;
    }
    if(bun!=p)
    {
        schimb(p,bun);
        coboara(bun);
    }
}
void sterge()
{
    schimb(1,nh--);
    coboara(1);
}
void prim(){
    for(int i=2;i<=n;i++){
        d[i]=INF;
        adauga(i);
    }
    d[1]=0;
    adauga(1);
    while(nh>0){
        int x=h[1];
        cost+=d[x];
        sterge();
        poz[x]=-1;
        for(int p=lst[x];p!=0;p=urm[p]){
            y=vf[p];
            c=cst[p];
            if(poz[y]!=-1&&c<d[y]){
                d[y]=c;
                urca(poz[y]);
                pred[y]=x;
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>x>>y>>c;
        adauga1(x,y,c);
        adauga1(y,x,c);
    }
    prim();
    cout<<cost<<" "<<n-1<<"\n";
    for(int i=2;i<=n;i++){
        cout<<pred[i]<<" "<<i<<"\n";
    }
    return 0;
}