#include <fstream>
#include <vector>
#include <queue>
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], APMCOST;
bool B[200002];
vector <PII> G[200002], APM;
priority_queue <PII, vector<PII>, greater<PII> > Q;

void Prim(int k);

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();
    is.close();
}

void Prim(int k)
{
    for (int i = 2; i <= N; ++i) D[i] = 1<<25;
    D[k] = 0;
    Q.push({0, 1});
    for (;!Q.empty();)
    {
        k = Q.top().y;
        B[k] = 1;
        for (const auto& next : G[k])
        {
            if (B[next.x]);
            else
                if (D[next.x] > next.y)
                {
                    D[next.x] = next.y;
                    T[next.x] = k;
                    Q.push({next.y, next.x});
                }
        }
        APM.push_back({T[k], k});
        APMCOST += D[k];
        while (!Q.empty() && B[Q.top().y])
            Q.pop();
    }
    os << APMCOST << '\n' << APM.size()-1 << '\n';
    for (int i = 1; i < APM.size(); ++i)
        os << APM[i].x << ' ' << APM[i].y << '\n';
};