#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], rank1[nMax];
vector<tuple<int,int,int>> edges;
vector<pair<int,int>> apm;

int findParent(int node)
{
    if (parent[node] == node)
        return node;
    parent[node]=findParent(parent[node]);
    return parent[node];
}

void unionSets(int a, int b)
{
    parent[findParent(a)]=findParent(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 (findParent(a) != findParent(b))
        {
            unionSets(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";
}