#include <bits/stdc++.h>
#define nmax 100005
using namespace std;

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

int n,m,tcost,d[nmax];

struct str
{
    int a,b,cost;
    bool operator <(const str &other)const
    {
        return cost>other.cost;
    }
};

vector<pair<int,int>>edges;
priority_queue<str>Q;

int dad(int nod)
{
    if (d[nod]==nod)
        return nod;
    return d[nod]=dad(d[nod]);
}
void unio(int x,int y)
{
    d[dad(x)]=dad(y);
}

int main()
{
    f>>n>>m;
    for (int i=1; i<=n; ++i)
        d[i]=i;
    for (int i=1; i<=m; ++i)
    {
        int xc,a,b;
        f>>a>>b>>xc;
        Q.push({a,b,xc});
    }
    while (!Q.empty())
    {
        int n1=Q.top().a;
        int n2=Q.top().b;
        int cc=Q.top().cost;
        Q.pop();
        if (dad(n1)!=dad(n2))
        {
            unio(n1,n2);
            tcost+=cc;
            edges.push_back({n1,n2});
        }
    }
    g<<tcost<<'\n'<<edges.size()<<'\n';
    for (auto w:edges)
    {
        g<<w.first<<' '<<w.second<<'\n';
    }
    return 0;
}