#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#include <deque>
#include <algorithm>
#define Nmax 200005
#define INF 0x3f3f3f3f
#define ll long long
#define MOD 1999999973

using namespace std;

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

int n, m;
int tt[Nmax];
ll ans;
struct edge{
int x, y, c;
}v[2*Nmax];
vector <pair <int, int> > sol;

bool cmp(edge a, edge b)
{
    return a.c < b.c;
}

int root(int x)
{
    int r=x;
    while (r!=tt[r]) r=tt[r];

    while (x!=tt[x])
    {
        int y=tt[x];
        tt[x]=r;
        x=y;
    }
    return r;
}

int main()
{
    f >> n >> m;

    for (int i = 1, x, y, c; i <= m; i++)
    {
        f >> x >> y >> c;
        v[i]={x, y, c};
    }

    sort (v+1, v+m+1, cmp);

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

    // cout << root(n) << '\n';;

    for (int i = 1; i <= m; i++)
    {
        int x=v[i].x, y=v[i].y, c=v[i].c;
        // cout << x << " " << y << '\n';
        int X=root(x), Y=root(y);
        if (X!=Y)
        {
            tt[X]=Y;
            ans+=c;
            sol.push_back({x, y});
        }
    }

    g << ans << '\n' << n-1 << '\n';

    for (auto i:sol) g << i.first << " " << i.second << '\n';

    return 0;
}