#include <fstream>
#include <map>
#include <climits>
#include <fstream>
#include <vector>
#include <stack>
#include <cmath>
#include <bitset>
#include <chrono>
#include <random>
#include <algorithm>
#include <set>
#include <queue>

using namespace std;

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

const int MOD = 1e9+7;

struct DSU {
	vector<int> e;
	DSU(int N) { e = vector<int>(N, -1); }

	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }

	bool same_set(int a, int b) { return get(a) == get(b); }

	int size(int x) { return -e[get(x)]; }

	bool unite(int x, int y) {
		x = get(x), y = get(y);
		if (x == y) return false;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y];
		e[y] = x;
		return true;
	}
};

vector<pair<int, pair<int, int>>> node;

void solve()
{
    int n, m; cin >> n >> m;

    for(int z=0;z<m;z++)
    {
        int a,b,c;cin>>a>>b>>c;
        node.push_back(make_pair(c, make_pair(a, b)));
    }

    sort(node.begin(), node.end());

    DSU v(n+1);

    vector<pair<int, int>> ans;

    int cost = 0;

    for(int z = 0; z < m; z++)
    {
        if(!v.same_set(node[z].second.first, node[z].second.second))
        {
            v.unite(node[z].second.first, node[z].second.second);
            ans.push_back(make_pair(node[z].second.first, node[z].second.second));
            cost += node[z].first;
        }
    }

    cout << cost << '\n';

    cout << n-1 << '\n';

    for(auto x : ans)
        cout<<x.first << ' ' << x.second << '\n';
}

int main()
{
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    int tt = 1; //cin >> tt;

    while(tt--)
        solve();
}