#include <bits/stdc++.h>

using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second

#define NMAX 200005
#define MOD 1999999973
#define INF 0x3f3f3f3f

int n, m, root[NMAX], MSTcost;
vector<pii> MST;
vector<tuple<int, int, int>> tree;

void read()
{
    in >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y, c;
        in >> x >> y >> c;
        tree.push_back({c, x, y});
    }
}

int getRoot(int i)
{
    if (root[i]==i)
        return i;
    return root[i] = getRoot(root[i]);
}

void setUnion(int x, int y)
{
    root[root[x]] = root[y];
}

void Kruskal()
{
    sort(tree.begin(), tree.end());

    for (int i = 1; i <= n; i++)
        root[i] = i;

    for (auto e : tree)
    {
        int x, y, wt;
        tie(wt, x, y) = e;
        getRoot(x);
        getRoot(y);
        if (root[x] != root[y])
        {
            setUnion(x, y);
            MST.push_back({x, y});
            MSTcost+=wt;
            if (MST.size()==n-1)
                return;
        }
    }
}

void solve()
{
    Kruskal();
    out<<MSTcost<<'\n'<<MST.size()<<'\n';
    for (auto e : MST)
        out<<e.fi<<' '<<e.se<<'\n';


}

int main()
{
    read();
    solve();
    return 0;
}