#include <cstring>
#include <queue>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

#define PII pair<int,int>
#define x first
#define y second

ifstream is("apm.in");
ofstream os("apm.out");

int N, M;

int D[200002], T[200002], COST = 0;
bool B[200002];

vector <PII> G[200002], APM;
priority_queue <PII, vector<PII>, greater<PII> > Q; // COST si NOD

void Prim(int node);

int main()
{
    is >> N >> M;
    for (int i = 1, a, b, c; i <= M; ++i)
    {
        is >> a >> b >> c;
        G[a].push_back({b, c});
        G[b].push_back({a, c});
    }
    Prim(1);
    is.close();
    os.close();
}

void Prim(int k)
{
    memset(D, 0x3f3f3f3f, sizeof(D));
    Q.push({0, k});
    D[k] = 0;
    for (; !Q.empty();)
    {
        k = Q.top().y;
        B[k] = 1;
        for (const auto& next : G[k])
        {
            if (B[next.x]) continue;
            if (D[next.x] > next.y)
            {
                D[next.x] = next.y;
                T[next.x] = k;
                Q.push({D[next.x], next.x});
            }
        }
        APM.push_back({T[k], k}); COST += D[k]; //update la APM, si la COST
        while (!Q.empty() && B[Q.top().y])
            Q.pop();
    }
    os << COST << '\n' << APM.size()-1 << '\n'; // -1 pentru ca prima muchie e 0-1
    for (int i = 1; i < APM.size(); ++i)
        os << APM[i].x << ' ' << APM[i].y << '\n'; // afisare muchii APM

};