#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 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;
    H_insert(1);
    while(hdim)
    {
        nod = H_extract();
        VIZ[nod] = 1;
        CostAPM+=D[nod];
        for(size_t i=0;i<G[nod].size();i++)
        {
            fiu = G[nod][i].first;
            cost = G[nod][i].second;
            if(D[fiu] > cost)
            {
                D[fiu] = cost;
                T[fiu] = nod;
                if(VIZ[fiu] == 0)
                {
                    if(P[fiu]==0)
                        H_insert(fiu);
                    else
                        H_up(P[fiu]);
                }
            }
        }
    }
    fout<<CostAPM<<'\n'<<n-1<<'\n';
    for(i=2;i<=n;i++)
        fout<<i<<' '<<T[i]<<'\n';
    return 0;
}
//struct muchie{int c,a,b;}M[Ndim];
//int DSJ[Ndim];
//vector < pair <int,int> > SOL;
//bool cmp(muchie x, muchie y)
//{
//    return x.c<y.c;
//}
//int root(int x)
//{
//    while(DSJ[x]>0)
//        x = DSJ[x];
//    return x;
//}
//int main()
//{
//    int n,m,i,a,b,c,nrm = 0,CostAPM=0,r1,r2;
//    fin>>n>>m;
//    for(i=1;i<=m;i++)
//    {
//        fin>>a>>b>>c;
//        M[++nrm].c = c;
//        M[nrm].a = a;
//        M[nrm].b = b;
//    }
//    for(i=1;i<=n;i++)
//        DSJ[i] = -1;
//    sort(M+1,M+nrm+1,cmp);
//    for(i=1;i<=m;i++)
//    {
//        r1 = root(M[i].a);
//        r2 = root(M[i].b);
//        if(r1!=r2)
//        {
//            if(DSJ[r1]>DSJ[r2])
//                swap(r1,r2);
//            DSJ[r1]+=DSJ[r2];
//            DSJ[r2] = r1;
//            CostAPM += M[i].c;
//            SOL.push_back(make_pair(M[i].a,M[i].b));
//        }
//    }
//    fout<<CostAPM<<'\n'<<n-1<<'\n';
//    for(i=0;i<n-1;i++)
//        fout<<SOL[i].first<<' '<<SOL[i].second<<'\n';
//    return 0;
//}