#include <bits/stdc++.h>
#define NMAX 200004

using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");

struct Muchie
{
    int x, cost, tata;
};

struct comparare
{
    bool operator() (const Muchie & a, const Muchie & b)
    {
        return a.cost > b.cost;
    }
};

int n, m, cost;
int tata[NMAX];
bool viz[NMAX];
vector < pair <int, int> > G[NMAX], sol;
priority_queue <Muchie, vector<Muchie>, comparare> H;

void citire();
void Prim(int start);
void afisare();

int main()
{
    citire();
    Prim(1);
    afisare();
    return 0;
}

void citire()
{
    int x, y, c;
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y >> c;
        G[x].push_back({y, c});
        G[y].push_back({x, c});
    }
}

void Prim(int start)
{
    Muchie M;
    H.push({start, 0, 0});

    while (!H.empty())
    {
        M = H.top();
        H.pop();
        if (viz[M.x])
            continue;
        viz[M.x] = 1;
        cost += M.cost;
        tata[M.x] = M.tata;
        sol.push_back({M.x, tata[M.x]});

        for (int i = 0; i < G[M.x].size(); i++)
        {
            int vf = G[M.x][i].first;
            if (viz[vf] == 0)
            {
                int cost = G[M.x][i].second;
                H.push({vf, cost, M.x});
            }
        }
    }
}

void afisare()
{
    fout << cost << '\n';
    fout << sol.size() - 1 << '\n';
    for (int i = 1; i < sol.size(); i++)
        fout << sol[i].first << ' ' << sol[i].second << '\n';;
}