#include <fstream>
#include <vector>
#include <algorithm>
const int NMAX=200005;

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct edge
{
    int a, b, c;
    bool operator<(const edge& other) const
    {
        return c<other.c;
    }
};

void mst();
int find(int);
bool unite(int, int);

int n, m;
vector <edge> mm;
vector <pair<int, int>> ans;
int t[NMAX];

int main()
{
    int i, a, b, c;
    fin>>n>>m;
    for(i=1; i<=n; i++) t[i]=i;
    for(i=1; i<=m; i++)
    {
        fin>>a>>b>>c;
        mm.push_back({a, b, c});
    }
    mst();
    return 0;
}

void mst()
{
    int i=0, cost=0;
    sort(mm.begin(), mm.end());
    while(i<int(mm.size()))
    {
        if(unite(mm[i].a, mm[i].b))
        {
            ans.push_back({mm[i].a, mm[i].b});
            cost+=mm[i].c;
        }
        i++;
    }
    fout<<cost<<'\n';
    fout<<ans.size()<<'\n';
    for(auto i:ans) fout<<i.first<<' '<<i.second<<'\n';
}

bool unite(int a, int b)
{
    int fa=find(a), fb=find(b);
    if(fa==fb) return false;
    else if(fa>fb) t[fb]=fa;
    else t[fa]=fb;
    return true;
}

int find(int nod)
{
    if(t[nod]==nod) return nod;
    t[nod]=find(t[nod]);
    return t[nod];
}