#include<stdio.h>
#include<vector>
#include<set>
using namespace std;
#define nmax 200005
#define inf 2000
struct element{long n, c;};
struct element2{long an, val;};
long a, b, c, rez, i, n, m;
vector <element> ma[nmax];
vector <element> ::iterator it;
element el;
set <pair <long, long> > h;
pair <long, long> pr;
element2 cmin[nmax];
bool fol[nmax];

void citire()
{
    scanf("%ld %ld",&n,&m);
    for (i=1;i<=m;i++)
    {
        scanf("%ld %ld %ld",&a,&b,&c);
        el.n=b; el.c=c;     ma[a].push_back(el);
        el.n=a; el.c=c;     ma[b].push_back(el);
    }
}

void rezolvare()
{
    for (i=1;i<=n;i++)
        cmin[i].val=inf;
    cmin[1].val=0;
    h.insert(make_pair(0,1));
    while (h.size())
    {
        pr=*h.begin();  h.erase(h.begin());
        rez+=pr.first;  fol[pr.second]=1;
        for (it=ma[pr.second].begin();it!=ma[pr.second].end();it++)
            if (!fol[(*it).n])
                if (cmin[(*it).n].val>(*it).c)
                {
                    h.erase(make_pair(cmin[(*it).n].val,(*it).n));
                    cmin[(*it).n].val=(*it).c;  cmin[(*it).n].an=pr.second;
                    h.insert(make_pair(cmin[(*it).n].val,(*it).n));

                }
    }
}

void afisare()
{
    printf("%ld\n",rez);
    printf("%ld\n",n-1);
    for (i=2;i<=n;i++)
        printf("%ld %ld\n",cmin[i].an,i);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire();
    rezolvare();
    afisare();
    return 0;
}