#include <bits/stdc++.h>

using namespace std;

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

int n, m, totweight;
vector <pair< int, pair<int, int >>> edges;
vector <pair <int, int >> mst;
vector <int > parent;

int find(int nod)
{
    if(parent[nod] == nod)
        return nod;
    return parent[nod] = find(parent[nod]);
}
void Kruskal()
{
    for(auto edge : edges)
    {
        int weight = edge.first;
        int u = edge.second.first;
        int v = edge.second.second;
        
        int parentu = find(u);
        int parentv = find(v);
        
        if(parentv != parentu)
        {
            mst.push_back({v, u});
            totweight += weight;
            parent[parentu] = parentv;
        }
        
    }
}
int main()
{
    f >> n >> m;
    for(int i = 1;i <= m;i ++)
    {
        int x, y, w;
        f >> x >> y >> w;
        edges.push_back({w, {x, y}});
    }
    
    for(int i = 0;i <= n;i ++)
        parent.push_back(i);
    
    sort(edges.begin(), edges.end());    
    Kruskal();
    
    g << totweight<<'\n' <<mst.size()<<'\n';
    
    for(auto i : mst)
        g << i.first <<" "<<i.second <<'\n';
    return 0;
}