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

#define NMax 200005
#define MMax 400005

ifstream f("apm.in");
ofstream g("apm.out");

struct muchie{int x,y,c;};

int n,m;
int tata[NMax];
long long sum;
muchie M[MMax];

vector<muchie> sol;

bool Compare(muchie i,muchie j) {return i.c<j.c;}

int query(int x)
{
    if(!tata[x]) return x;
    tata[x]=query(tata[x]);
    return tata[x];
}

void update(int x,int y)
{
    tata[y]=x;
}

int main()
{
    int i,q1,q2;

    f>>n>>m;
    for(i=1;i<=m;i++) f>>M[i].x>>M[i].y>>M[i].c;

    sort(M+1,M+m+1,Compare);

    for(i=1;i<=m;i++)
    {
        q1=query(M[i].x);
        q2=query(M[i].y);

        if(q1!=q2)
        {
            sum+=(long long)M[i].c;
            sol.push_back(M[i]);
            update(q1,q2);
        }
    }

    g<<sum<<"\n"<<sol.size()<<"\n";
    for(i=0;i<(int)sol.size();i++) g<<sol[i].x<<" "<<sol[i].y<<"\n";

    f.close();
    g.close();
    return 0;
}