#include <bits/stdc++.h>
#include <vector>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");
//#define f cin
//#define g cout
int n, m, t[200010], r[200010], c, a, b, sum;
int root(int nod)
{
    int start=nod;
    while(t[nod]!=0)
    {
        nod=t[nod];
    }
    int aux=nod;
    while(t[start]!=0)
    {
        aux=t[start];
        t[start]=nod;
        start=aux;
    }
    return nod;
}
void join(int ax, int bx)
{
    //cout<<ax<<bx;
    int a=root(ax);
    int b=root(bx);
    if(ax==bx)
        return;
    if(r[a]>r[b])
    {
        t[b]=a;
    }
    else
    {
        if(r[a]==r[b])
            r[b]++;
        t[a]=b;
    }
}

struct edge
{
    int x, y, c;
    bool operator < (const edge &o)
    {
        return c<o.c;
    }
};
edge v[200100];
int main()
{
    f>>n>>m;
    for(int i=1;i<=n;i++)
    {
        r[i]=1;
    }
    for(int i=1;i<=m;i++)
    {
        f>>v[i].x>>v[i].y>>v[i].c;
    }
    sort(v+1, v+m+1);
    vector<edge> sol;
    for(int i=1;i<=m;i++)
    {
        if(root(v[i].x)!=root(v[i].y))
        {
            sol.push_back(v[i]);
            sum+=v[i].c;
            join(v[i].x, v[i].y);
        }
    }
    g<<sum<<endl<<sol.size()<<endl;
    for(int i=0;i<sol.size();i++)
    {
        g<<sol[i].y<<" "<<sol[i].x<<endl;
    }


    return 0;
}