#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

struct muchie
{
    int x, y, c;
};

ifstream in("apm.in");
ofstream out("apm.out");
int n, m;
muchie v[400005];
int p[200005];
int rang[200005];
vector<pair<int, int>> ans;
long long sum;

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

int rad(int x)
{
    if(p[x] == x)
    {
        return x;
    }
    else
    {
        int r = rad(p[x]);
        p[x] = r;
        return r;
    }
}

void reuniune(int x, int y)
{
    int rx = rad(x);
    int ry = rad(y);

    if(rang[rx] > rang[ry])
    {
        p[ry] = rx;
    }
    else
    {
        p[rx] = ry;

        if(rang[rx] == rang[ry])
        {
            rang[ry]++;
        }
    }
}

int verif(int x, int y)
{
    int rx = rad(x);
    int ry = rad(y);

    if(rx == ry)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

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

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

    for(int i = 1; i<=n; i++)
    {
        p[i] = i;
    }

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

    for(int i = 1; i<=m && ans.size() < n-1; i++)
    {
        //out<<v[i].x<<" "<<v[i].y<<" "<<v[i].c<<'\n';

        if(!verif(v[i].x, v[i].y))
        {
            sum += v[i].c;
            reuniune(v[i].x, v[i].y);
            ans.push_back({v[i].x, v[i].y});
        }
    }

    out<<sum<<'\n'<<ans.size()<<'\n';

    for(auto i: ans)
    {
        out<<i.first<<" "<<i.second<<'\n';
    }

    return 0;
}