#include <fstream>
#include <queue>
#include <iostream>

using namespace std;

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

#define Nmax 400000

struct nod
{
    int a, b, d;
};

nod v[Nmax];

struct compare
{
    bool operator()(const nod& l, const nod& r)
        {
        return l.d > r.d;
        }
};

priority_queue<int, vector<nod>, compare > q;

void insertqueue(int x, int *viz, int m)
{
    for(int i = 0; i < m; i++)
        {
        if(v[i].a == x && (viz[v[i].a] != viz[v[i].b]))
            q.push(v[i]);
        if(v[i].b == x && (viz[v[i].a] != viz[v[i].b]))
            {
            int temp = v[i].a;
            v[i].a = v[i].b;
            v[i].b = temp;
            q.push(v[i]);
            }
        }
}

void prim( int n, int m, int x)
{
    int i, s = 0, c = 0, nr = 0, k = 0;
    int *viz = new int[n + 1];
    nod t;
    pair<int, int> *muchii = new pair<int, int>[n];
    for(i = 0; i < n; i++)
        viz[i] = i;

    insertqueue(x, viz, m);

    while(c < n - 1)
        {
        t = q.top();

        while(viz[t.a] == viz[t.b])
            {
            q.pop();
            t = q.top();
            }

        muchii[k].first = t.a;
        muchii[k].second = t.b;
        k++;
        s += t.d;
        nr++;

        if(!q.empty())
            q.pop();

        viz[t.b] = x;

        insertqueue(t.b, viz, m);
        c++;
        }
    g << s << "\n";
    g << k << "\n";

    for(i = 0; i < k; i++)
        g << muchii[i].first << " " << muchii[i].second << "\n";

    delete[] muchii;
    delete[] viz;
}

int main()
{
    int n, m, i;

    f >> n >> m;

    for(i = 0; i < m; i++)
        {
        f >> v[i].a >> v[i].b >> v[i].d;
        }

    prim(n, m, 1);

    return 0;
}