#include<algorithm>
using namespace std;
#include<vector>

#define DIM 200005
#define pb push_back
#define mp make_pair
#define x first.first
#define y first.second
#define sc second
#define fs first

int n,t[DIM],r[DIM];
vector <pair <pair<int,int> ,int> > lst;
vector <pair<int,int> > sol;

struct cmp
{
    bool operator () (const pair <pair<int,int> ,int> &a,const pair <pair<int,int> ,int> &b) const
    {
        return a.sc<b.sc;
    }
};

int find (int &a)
{
    if(t[a]!=a)
        t[a]=find(t[a]);
    return t[a];
}

inline void unite (int a,int b)
{
    if(r[a]<=r[b])
    {
        t[a]=b;
        r[b]+=r[a];
    }
    else
    {
        t[b]=a;
        r[a]+=r[b];
    }
}

int main ()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int nr1,nr2,nr3,i,m,t1,t2;

    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d%d",&nr1,&nr2,&nr3);
        lst.pb (mp (mp (nr1,nr2),nr3));
    }

    sort(lst.begin (),lst.end (),cmp ());

    for(i=1;i<=n;++i)
    {
        r[i]=1;
        t[i]=i;
    }

    m=lst.size ();
    int nr=0;
    for(i=0;i<m;++i)
    {
        t1=find(lst[i].x);
        t2=find(lst[i].y);
        if(t1!=t2)
        {
            unite(t1,t2);
            sol.pb (mp (lst[i].y,lst[i].x));
            nr+=lst[i].sc;
        }
    }
    printf("%d\n%d\n",nr,(int)sol.size ());
    m=sol.size ();
    for(i=0;i<m;++i)
        printf("%d %d\n",sol[i].fs,sol[i].sc);
    return 0;
}