#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

int find_tata(int x, vector<int>&tata)
{
    if(tata[x] == 0)
        return x;
    return tata[x] = find_tata(tata[x], tata);
}
void uneste(int x, int y, vector<int>&tata)
{
    int tx = find_tata(x, tata);
    int ty = find_tata(y, tata);
    tata[ty] = tx;
}
int kruskal(vector<pair<int, pair<int, int>>>&adj, vector<int>&tata, int n, vector<pair<int, int>>&sol)
{
    int m = 0;
    int cost = 0;
    for(auto edge : adj)
    {
        int x = edge.second.first;
        int y = edge.second.second;

        if(find_tata(x, tata) != find_tata(y, tata))
        {
            uneste(x, y, tata);
            sol.push_back({x, y});
            cost+=edge.first;
            m++;
            if(m == n-1)
                return cost;
        }
    }
}
int main()
{
    int n, m;
    fin >> n >> m;
    vector<pair<int, pair<int, int>>> adj;

    for(int i = 0; i < m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        adj.push_back({c, {x, y}});
    }

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

    vector<int>tata(n+1);

    vector<pair<int, int>>sol;
    fout << kruskal(adj, tata, n, sol)<< "\n" << n-1 << "\n";

    for(auto e : sol)
    {
        fout << e.second << " " << e.first << "\n";
    }
    return 0;
}