#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
ifstream in("../apm.in");
ofstream out("../apm.out");
 
int n, m;
int suma = 0;
 
const int NMAX = 200005;
 
int tati[NMAX];
 
struct edge
{
    int x, y, cost;
};
 
vector <edge> graf;
vector <pair <int, int> > Sol;
 
void initTati(int x)
{
    for(int i = 1; i <= x; i++)
        tati[i] = i;
}
 
void citire()
{
    in >> n >> m;
     
    initTati(n);
     
    for(int i = 0; i < m; i++)
    {
        int a, b, c;
        in >> a >> b >> c;
        graf.push_back({a, b, c});
    }
}
 
bool cmp(const edge &a, const edge &b)
{
    return a.cost < b.cost;
}
 
int getRoot(int nod)
{
    if(nod == tati[nod])
        return nod;
    return( tati[nod] = getRoot(tati[nod]) );
}
 
bool areUnited(int x, int y)
{
    return getRoot(x) == getRoot(y);
}
 
void unite(int x, int y)
{
    tati[getRoot(x)] = getRoot(y);
}
 
void solve()
{
    sort(graf.begin(), graf.end(), cmp);
    /*for(int i = 0; i < graf.size(); i++)
    {
        cout << graf[i].x << " " << graf[i].y << " " << graf[i].cost << "\n";
         
    }*/
    for(edge e : graf)
    {
        if(!areUnited(e.x, e.y))
        {
            unite(e.x, e.y);
            Sol.push_back(make_pair(e.y, e.x));
            suma += e.cost;
        }
    }
}
int main()
{
    citire();
    solve();
    out << suma << "\n";
    out << Sol.size()<< "\n";
    for(auto e : Sol)
    {
        out << e.first << " " << e.second << "\n";
    }
    return 0;
}