#include <fstream>
#include <vector>
#include <bitset>
#include <queue>

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

int sum, nrsol, a[400005], b[400005], c[400005];
vector <int> e[200005];
priority_queue <pair <int, int>, vector<pair <int, int> >, greater<pair <int, int> > > edges;
bitset <200005> added;
bitset <400005> sol;
int main()
{
    int n, m;
    cin >> n >> m;

    for(int i = 1; i <= m; ++i)
    {
        cin >> a[i] >> b[i] >> c[i];
        e[a[i]].push_back(i);
        e[b[i]].push_back(i);
    }

    added[1] = true;

    for(auto it = e[1].begin(); it != e[1].end(); ++it)
    {
        edges.push({c[*it], *it});
    }

    while(!edges.empty())
    {
        int i = edges.top().second;
        edges.pop();

        if(added[a[i]] == true && added[b[i]] == true)
            continue;

        int x;

        if(added[a[i]] == false)
            x = a[i];
        else
            x = b[i];

        added[x] = true;
        sum += c[i];
        ++nrsol;
        sol[i] = true;

        for(auto it = e[x].begin(); it != e[x].end(); ++it)
        {
            if(added[a[*it]] == true && added[b[*it]] == true)
                continue;

            edges.push({c[*it], *it});
        }
    }

    cout << sum << '\n' << nrsol << '\n';

    for(int i = 1; i <= m; ++i)
    {
        if(sol[i] == true)
            cout << a[i] << ' ' << b[i] << '\n';
    }

    return 0;
}