#include<cstdio>
#include<algorithm>
#include<vector>
#define nmax 200005
#define inf (1<<30)
using namespace std;
int a[nmax],sum,d[nmax],h[nmax*2+100],poz[nmax],n,m,l;
vector <pair<int,int> > g[nmax],sol;
void InApm(int x)
{
int i;
for(i=0;i<g[x].size();++i)
    {
     int nod=g[x][i].first;
     int cost=g[x][i].second;
     d[nod]=min(d[nod],cost);
     if (d[nod]==cost) a[nod]=x;
    }
}

void push(int k)
{
    while((k * 2 <= l && d[h[k]] > d[h[k * 2]]) || (k * 2 + 1 <= l && d[h[k]] > d[h[k * 2 + 1]]))
    {
        if (d[h[k * 2]] < d[h[k * 2 + 1]] || k * 2 + 1 > l)
        {
            swap(h[k],h[k * 2]);
            swap(poz[h[k]],poz[h[k * 2]]);
            k *= 2;
        }
        else
        {
            swap(h[k],h[k * 2 + 1]);
            swap(poz[h[k]],poz[h[k * 2 + 1]]);
            k = k * 2 + 1;
        }
    }
}


void pop(int k)
{
    while(k > 1 && d[h[k]] < d[h[k / 2]])
    {
        swap(h[k],h[k / 2]);
        swap(poz[h[k]],poz[h[k / 2]]);
        k = k / 2;
    }
}

void InHeap(int nod)
{
    h[++l] = nod;
    poz[nod] = l;
    pop(l);
}

int OutHeap()
{
    int x = h[1];
    swap(h[1],h[l]);
    swap(poz[h[1]],poz[h[l]]);
    l--;
    push(1);
        poz[x] = 0;
    return x;
}
void read()
{
int x,y,c,i;
freopen("apm.in","r",stdin);
scanf("%d %d\n",&n,&m);
for(i=1;i<=m;++i)
    {
    scanf("%d %d %d",&x,&y,&c);
    g[x].push_back(make_pair(y,c));
    g[y].push_back(make_pair(x,c));
    }
}
void prim()
{
int i,x,j,nod;
for (i=1;i<=n;++i) d[i]=inf;
d[1]=0;InApm(1);

for (i=2;i<=n;++i) InHeap(i);
for (i=1;i<n;++i)
    {
     x=OutHeap();
     InApm(x);
     sum+=d[x];
     sol.push_back(make_pair(x,a[x]));
     for (j=0;j<g[x].size();++j)
        {
         nod=g[x][j].first;
         if (poz[nod]) pop(poz[nod]);
        }
    }
}
void write()
{
freopen("apm.out","w",stdout);
int i;
printf("%d\n%d\n",sum,n-1);
for(i=0;i<n-1; ++i)
printf("%d %d\n",sol[i].first,sol[i].second);
}
int main()
{
read();
prim();
write();
return 0;
}