#include <bits/stdc++.h>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

const int N=2e5+10,INF=1e7+10;

vector <pair<int,int>> a[N];
int n,cost,pred[N],d[N],h[N],poz[N],nh;

void schimba(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]])
    {
        schimba(p,p/2);
        p=p/2;
    }
}

void coboara(int p)
{
    int fs=2*p,fd=2*p+1,optim=p;
    if(fs<=nh && d[h[fs]]<d[h[optim]])
    {
        optim=fs;
    }
    if(fd<=nh && d[h[fd]]<d[h[optim]])
    {
        optim=fd;
    }
    if(optim!=p)
    {
        schimba(p,optim);
        coboara(optim);
    }
}

void sterge(int p)
{
    if(p==nh)
    {
        nh--;
    }
    else
    {
        schimba(p,nh);
        poz[h[nh]] = -1;
        nh--;
        urca(p);
        coboara(p);
    }
}

void apm()
{
    for(int i=1;i<=n;i++)
    {
        d[i]=INF;
        h[++nh]=i;
        poz[i]=nh;
    }
    d[1]=0;
    urca(poz[1]);
    while(nh>0)
    {
        int x=h[1];
        sterge(1);
        for(auto i:a[x])
        {
            int y=i.first;
            int c=i.second;
            if(poz[y] != -1 && c < d[y])
            {
                d[y]=c;
                pred[y]=x;
                urca(poz[y]);
            }
        }
    }
}

int main()
{
    int m;
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        f>>x>>y>>z;
        a[x].push_back({y,z});
        a[y].push_back({x,z});
    }
    apm();
    for(int i=1;i<=n;i++)
    {
        cost+=d[i];
    }
    g<<cost<<"\n"<<n-1<<"\n";
    for(int i=2;i<=n;i++)
    {
        g<<i<<" "<<pred[i]<<"\n";
    }
    return 0;
}