#include <iostream>
#include <fstream>

#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#if __cplusplus > 199711L
#include <unordered_map>
#include <unordered_set>
#endif

#include <cstdio>
#include <ctime>
#include <cmath>
#include <cstring>
#include <cstdlib>

using namespace std;

typedef long long int64;

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

const int MMAX = 400010;

int N, M;
int LL[MMAX], height[MMAX];
vector<pair<int, int> > apm_edges;

struct Edge { int X, Y, C; } edges[MMAX];
struct compare
{
    bool operator()(const Edge &lhs, const Edge &rhs) const
    {
        return (lhs.C < rhs.C);
    }
};

int _find(int x)
{
    int ret;
    for (ret = x; ret != LL[ret]; ret = LL[ret]);

    int y;
    for ( ; x != LL[x]; )
    {
        y = LL[x];
        LL[x] = ret;
        x = y;
    }

    return ret;
}

void unite(int x, int y)
{
    if (height[x] > height[y]) LL[y] = x;
    else LL[x] = y;

    if (height[x] == height[y]) ++height[y];
}

int main()
{
    int i, res = 0;

    fin >> N >> M;

    for (i = 1; i <= N; ++i)
        height[i] = 1, LL[i] = i;

    for (i = 1; i <= M; ++i)
        fin >> edges[i].X >> edges[i].Y >> edges[i].C;

    sort(edges + 1, edges + M + 1, compare());

    for (i = 1; i <= M; ++i)
    {
        if (_find(edges[i].X) == _find(edges[i].Y)) continue;
        apm_edges.push_back(make_pair(edges[i].X, edges[i].Y));
        res += edges[i].C;
        unite(_find(edges[i].X), _find(edges[i].Y));
    }

    fout << res << '\n' << apm_edges.size() << '\n';
    for (i = 0; i < (int)apm_edges.size(); ++i)
        fout << apm_edges[i].first << ' ' << apm_edges[i].second << '\n';

	fin.close();
	fout.close();
	return 0;
}