#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>

using namespace std;

struct much
{
    int a, b, c;

    much(int _a, int _b, int _c)
        : a(_a), b(_b), c(_c) {}

    friend bool operator>(const much& m1, const much& m2)
    {
        return m1.c > m2.c;
    }
};

int N, M, C = 0;
vector<pair<int, int>> L[200001];
vector<much> MST;

void prim_mst(int s)
{
    bool viz[200001];
    viz[s] = true;
    priority_queue<much, vector<much>, greater<much>> q;
    
    for(const auto& [b, c] : L[s])
        q.push(much(s, b, c));

    while(!q.empty())
    {
        much m = q.top();
        q.pop();

        if(viz[m.a] != viz[m.b])
        {
            C += m.c;
            MST.push_back(m);

            int next = (viz[m.a] ? m.b : m.a);
            viz[next] = true;

            for(const auto& [b, c] : L[next])
                if(!viz[b])
                    q.push(much(next, b, c));
        }
    }

}

int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");

    fin >> N >> M;
    for(int i = 1; i <= M; i++)
    {
        int a, b, c;
        fin >> a >> b >> c;
        L[a].push_back({b, c});
        L[b].push_back({a, c});
    }

    prim_mst(1);

    fout << C << '\n' << N - 1 << '\n';

    for(const auto& e : MST)
        fout << e.a << ' ' << e.b << '\n';

    fin.close();
    fout.close();

    return 0;
}