#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;

ifstream fin ("prim.in");
ofstream fout ("prim.out");

using VI = vector<int>;
using PI = pair<int, int>;
using VP = vector <PI>;
using VVI = vector<VI>;
using VVP = vector<VP>;

const int maxn = 1001,
          inf = 0x3f3f3f3f;

struct Edge {
Edge() : node{0}, key{0}
{}
Edge(int node, int key) : node{node}, key{key}
{}

bool operator < (const Edge& a) const
{
    return key > a.key;
}
int node, key;
};

bitset <maxn> vizitat;
VVP G;
VI key, t;
int n, m;
VP apm;
long long cost_apm;


void ReadFunction();
void Prim(int x);
void WriteFunction();

int main()
{
    ReadFunction();
    Prim(1);
    WriteFunction();
}

void ReadFunction()
{
    fin >> n >> m;
    G = VVP(n + 1);
    int x, y, w;
    for (int i = 1; i <= m; ++i)
    {
        fin >> x >> y >> w;
        G[x].emplace_back(y, w);
        G[y].emplace_back(x, w);
    }
}

void Prim(int x)
{
    priority_queue <Edge> Q;
    t = VI(n + 1);
    key = VI(n + 1, inf);
    key[x] = 0;
    Q.push({x, 0});

    int y, w;
    while (!Q.empty())
    {
        x = Q.top().node;
        vizitat[x] = 1;
        for (const auto& p : G[x])
        {
            y = p.first;
            w = p.second;
            if (vizitat[y])
                continue;
            if (key[y] > w)
            {
                key[y] = w;
                t[y] = x;
                Q.emplace(y, w);
            }
        }
        apm.push_back({x, t[x]});
        cost_apm += key[x];

        while (!Q.empty() && vizitat[Q.top().node])
            Q.pop();
    }
}

void WriteFunction()
{
    fout << cost_apm << '\n';
    fout << apm.size() - 1 << '\n';

    for (size_t i = 1; i < apm.size(); ++i)
        fout << apm[i].first << ' ' << t[apm[i].first] << '\n';
}