#include <bits/stdc++.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
vector <int> afis1;
vector <int> afis2;
int a[400010],b[400010],c[400010],v[400010],h[200010],t[200010],n,m,t1,t2,cost,nr;
int tata (int j)
{
    while(t[j]!=j)
        j=t[j];
    return j;
}
bool cmp (int x,int y) {return c[x]<c[y];}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
       f>>a[i]>>b[i]>>c[i];
    for(int i=1;i<=m;i++) v[i]=i;
    sort(v+1,v+m+1,cmp);
    for(int i=1;i<=n;i++)
        h[i]=1,t[i]=i;
    for(int i=1;i<=m;i++)
    {t1=tata(a[v[i]]),t2=tata(b[v[i]]);
        if(t1!=t2)
            {cost=cost+c[v[i]];
             nr++;
             afis1.push_back(a[v[i]]);
             afis2.push_back(b[v[i]]);
            if(h[t1]>=h[t2])
            {
             h[t1]=h[t1]+h[t2];
             t[t2]=t1;
            }
            else
            {
                h[t2]=h[t1]+h[t2];
                t[t1]=t2;
            }
            }}
    g<<cost<<'\n'<<nr<<'\n';
    for(int i=0;i<afis1.size();i++)
        g<<afis1[i]<<" "<<afis2[i]<<'\n';
    return 0;}