#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<vector<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});
    }
}

bool comp(vector<int> a, vector<int> b)
{
    if (a[0]>b[0])
        return 0;
    return 1;
}

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

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

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

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

    for (auto e : tree)
    {
        int x, y, wt;
        x=e[1], y=e[2], wt=e[0];
        root[x] = getRoot(x);
        root[y] = 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;
}