#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#include<tuple>

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

const int nMax=200002;
const int mMax=400002;
int n,m, parent[nMax], h[nMax];
vector<tuple<int,int,int>> edges;
vector<pair<int,int>> apm;

int Find(int x)
{
    if (parent[x] == x) return x;
    parent[x]=Find(parent[x]);
    return parent[x];
}

void Union(int a, int b)
{
    a=Find(a);
    b=Find(b);
    if(h[a]<h[b])
        parent[a]=b;
    else if(h[a]>h[b]) parent[b]=a;
    else {parent[a]=b;
    h[b]++;}
}

int main()
{
    int totalCost=0;
    fin>>n>>m;
    for (int i=0; i<m; i++)
    {
        int a,b,cost;
        fin>>a>>b>>cost;
        edges.push_back({cost,a,b});
    }
    for (int i=1; i<=n; i++)
        parent[i]=i;

    sort(edges.begin(), edges.end());

    for (auto [cost,a,b]:edges)
    {
        if (Find(a) != Find(b))
        {
            Union(a,b);
            totalCost+=cost;
            apm.push_back({a,b});
        }
    }

    fout<<totalCost<<"\n";
    fout<<apm.size()<<"\n";
    for (auto [a,b]:apm)
        fout<<a<<" "<<b<<"\n";
}