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

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

/*
const int nMax=200002;
const int mMax=400002;
int n,m, parent[nMax], h[nMax];
vector<tuple<int,int,int>> edges;
vector<pair<int,int>> apm;

int Find(int x)
{
    if (parent[x] == x) return x;
    parent[x]=Find(parent[x]);
    return parent[x];
}

void Union(int a, int b)
{
    a=Find(a);
    b=Find(b);
    if(h[a]<h[b])
        parent[a]=b;
    else if(h[a]>h[b]) parent[b]=a;
    else {parent[a]=b;
    h[b]++;}
}

int main()
{
    int totalCost=0;
    fin>>n>>m;
    for (int i=0; i<m; i++)
    {
        int a,b,cost;
        fin>>a>>b>>cost;
        edges.push_back({cost,a,b});
    }
    for (int i=1; i<=n; i++)
        parent[i]=i;

    sort(edges.begin(), edges.end());

    for (auto [cost,a,b]:edges)
    {
        if (Find(a) != Find(b))
        {
            Union(a,b);
            totalCost+=cost;
            apm.push_back({a,b});
        }
    }

    fout<<totalCost<<"\n";
    fout<<apm.size()<<"\n";
    for (auto [a,b]:apm)
        fout<<a<<" "<<b<<"\n";
}
*/

struct Muchie {
    int nod;
    int cost;
};

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

    int n, m;
    fin >> n >> m;

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

    vector<int> viz(n + 1, 0);
    vector<pair<int, int>> sol;
    long long cost_total = 0;

    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> q;

    viz[1] = 1;
    for (auto e : G[1])
        q.push({e.cost, e.nod, 1});

    while (!q.empty() && sol.size() < n - 1) {
        auto [c, y, x] = q.top();
        q.pop();

        if (viz[y] == 0) {
            viz[y] = 1;
            cost_total += c;
            sol.push_back({x, y});

            for (auto e : G[y])
                if (viz[e.nod] == 0)
                    q.push({e.cost, e.nod, y});
        }
    }

    fout << cost_total << '\n';
    fout << sol.size() << '\n';
    for (auto p : sol)
        fout << p.first << " " << p.second << '\n';

    return 0;
}