#include <bits/stdc++.h>

using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");
const int NMAX = 2e5+5;
int link[NMAX],size[NMAX];
vector< tuple<int,int,int> > v, sol;

int find(int x)
{
    int R = x;
    while (R!=link[R])
        R = link[R];
    while (x!=link[x])
    {
        int aux = link[x];
        link[x] = R;
        x = aux;
    }
    return x;
}
void unite(int x, int y)
{
    x = find(x);
    y = find(y);
    if (size[x]<size[y])
        swap(x,y);
    size[x]+=size[y];
    link[y] = x;
}
bool same(int x, int y)
{
    return (find(x) == find(y));
}

int main()
{
    int n,m;
    in >> n >> m;
    for (int i = 1; i<=n; i++)
    {
        size[i] = 1;
        link[i] = i;
    }
    for (int i = 1; i<=m; i++)
    {
        int x,y,c;
        in >> x >> y >> c;
        v.push_back(make_tuple(c,x,y));
    }
    sort(v.begin(),v.end());
    int rez = 0;
    for (auto it: v)
    {
        int cost = get<0>(it);
        int x = get<1>(it);
        int y = get<2>(it);
        if (!same(x,y))
        {
            unite(x,y);
            rez+=cost;
            sol.push_back(it);
        }
    }
    out << rez << "\n" << sol.size() << "\n";
    for (auto it: sol)
    {
        int x = get<1>(it);
        int y = get<2>(it);
        out << x << " " << y << "\n";
    }
}