#include <fstream>
#include <algorithm>
#include <vector>

#define Ndim 200001
#define Mdim 400001
#define oo 200000200
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int D[Ndim],H[Ndim],P[Ndim],T[Ndim],hdim;
bool VIZ[Ndim];
vector < pair <int,int> > G[Ndim];
void apm_insert(int nod)
{
    for(size_t i=0;i<G[nod].size();i++)
    {
        int fiu = G[nod][i].first;
        int cost = G[nod][i].second;
        if(D[fiu]>cost)
        {
            D[fiu] = cost;
            T[fiu] = nod;
        }
    }
}
void H_up(int poz)
{
    int tata =poz/2;
    while(D[H[tata]] > D[H[poz]] && tata >= 1)
    {
        swap(H[tata],H[poz]);
        swap(P[H[tata]],P[H[poz]]);
        tata/=2;poz/=2;
    }
}
void H_down(int poz)
{
    int fiu = 2*poz;
    while(fiu <= hdim)
    {
        if(fiu+1 <= hdim && D[H[fiu]] > D[H[fiu+1]])
            fiu++;
        if(D[H[fiu]] < D[H[poz]])
        {
            swap(H[fiu],H[poz]);
            swap(P[H[fiu]],P[H[poz]]);
            poz = fiu;
            fiu = 2*poz;
        }
        else
            break;
    }
}
void H_insert(int x)
{
    H[++hdim] = x;
    P[x] = hdim;
    H_up(hdim);
}
int H_extract()
{
    int x = H[1];
    P[H[1]] = 0;
    H[1] = H[hdim];
    P[H[1]] = 1;
    hdim--;
    return x;

}
int main()
{
    int n,m,i,a,b,c,fiu,nod,cost,CostAPM=0;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        G[a].push_back(make_pair(b,c));
        G[b].push_back(make_pair(a,c));
    }
    for(i=2;i<=n;i++)
        D[i] = oo;
    for(i=1;i<=n;i++)
        H_insert(i);
    while(hdim)
    {
        nod = H_extract();
        apm_insert(nod);
        CostAPM+=D[nod];
        for(size_t i=0;i<G[nod].size();i++)
        {
            fiu = G[nod][i].first;
            if(P[fiu])
                H_up(P[fiu]);
        }
    }
    fout<<CostAPM<<'\n'<<n-1<<'\n';
    for(i=2;i<=n;i++)
        fout<<i<<' '<<T[i]<<'\n';
    return 0;
}