#include <bits/stdc++.h>

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
const int N = 200005;
struct triple
{
    int a,b,c;
};
vector<triple> muchii;
int link[N],size[N];
int find(int x)
{
    while (x!=link[x])
        x = link[x];
    return x;
}
void unite(int x, int y)
{
    x = find(x);
    y = find(y);
    if (size[y]>size[x])
        swap(x,y);
    size[x]+=size[y];
    link[y] = x;
}
bool comp(triple X, triple Y)
{
    return (X.c<Y.c);
}
int main()
{
    int n,m;
    in >> n >> m;
    for (int i = 1; i<=m; i++)
    {
        int x,y,cost;
        in >> x >> y >> cost;
        triple k;
        k.a = x; k.b = y; k.c = cost;
        muchii.push_back(k);
    }
    for (int i = 1; i<=n; i++)
    {
        link[i] = i;
        size[i] = 1;
    }
    sort(muchii.begin(),muchii.end(),comp);
    int ans = 0;
    vector< pair<int,int> > rez;
    for (int i = 0; i<muchii.size(); i++)
    {
        int x = muchii[i].a, y = muchii[i].b, cost = muchii[i].c;
        if (find(x)!=find(y))
        {
            ans+=cost;
            unite(x,y);
            rez.push_back(make_pair(x,y));
        }
    }
    out << ans << "\n" << rez.size() << "\n";
    for (int i = 0; i<rez.size(); i++)
        out << rez[i].second << " " << rez[i].first << "\n";
}