#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define nmax 400005
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int n,m,a[nmax],b[nmax],c[nmax],ind[nmax],tata[nmax],cont,muchii;
bool cmp(int i,int j)
{
    return c[i]<c[j];
}
struct eee
{
    int x,y;
};
int f(int nod)
{
    if(tata[nod]==nod)return nod;
    return tata[nod]=f(tata[nod]);
}
void unire(int x,int y)
{
    tata[f(x)]=f(y);
}
vector<eee> sol;
int main()
{
    in>>n>>m;
    for(int i=1;i<=m;i++)
    {
        in>>a[i]>>b[i]>>c[i];
        ind[i]=i;
    }
    for(int i=1;i<=n;i++)tata[i]=i;
    sort(ind+1,ind+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        int j=ind[i];
        if(f(a[j])!=f(b[j]))
        {
            unire(a[j],b[j]);
            muchii++;
            cont+=c[j];
            sol.push_back({a[j],b[j]});
        }
    }
    out<<cont<<'\n'<<muchii<<'\n';
    for(auto i:sol)out<<i.x<<' '<<i.y<<'\n';
    return 0;
}