#include <iostream>
#include<fstream>
#include<queue>
#include<algorithm>
using namespace std;

///kruskal cu paduri de arbori disjuncte - complexitate O(nlogm)
ifstream f("apm.in");
ofstream g("apm.out");
priority_queue <pair<int, pair<int, int>>> myheap;
pair<int,pair<int,int>> muchii[200005];
vector  <pair<int,int>> apm;
int tata[100007], grad[100007];

int find_father(int nod)
{
    if(tata[nod] == nod)
        return nod;
    tata[nod] = find_father(tata[nod]);
    return tata[nod];
}

void kruskal(int n, int m, int &cost, int &k)
{
    int i;
    cost = 0, k = 0;
    for(i = 1; i <= n; i++)
    {
        tata[i] = i;
        grad[i] = 1;
    }

    sort(muchii + 1, muchii + m + 1);

    for(i = 1; i <= m; i++)
        {
            int x = muchii[i].second.first;
            int y = muchii[i].second.second;
            if(find_father(x) != find_father(y))
            {
                int A = find_father(x);
                int B = find_father(y);
                if(grad[A] < grad[B])
                {
                    tata[A] = B;
                    grad[B] += grad[A];
                }
                else
                {
                    tata[B] = A;
                    grad[A] += grad[B];
                }
                cost = cost + muchii[i].first;
                k++;
                apm.push_back(make_pair(x,y));
            }
    }

}
int main()
{
    int n, m, i, a, b, c;
    f >> n >> m;
    for(i = 1; i <= m; i++)
    {
        f >> a >> b >> c;
        muchii[i] = make_pair(c, make_pair(a, b));
    }
    int cost, k;
    kruskal(n, m, cost, k);
    g << cost << "\n";
    g << k << "\n";
    for(i = 0; i < k; i++)
        g << apm[i].first << " " << apm[i].second << "\n";
    return 0;
}