#include <bits/stdc++.h>

using namespace std;

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

#define NMAX 200010
#define inf 0x3f3f3f3f

struct NodCost {
    int nod, cost;
};

struct Muchie {
    int from, to, cost;
    bool operator < (const Muchie &other) const
    {
        return cost > other.cost;
    }
};

vector<NodCost> G[NMAX];
priority_queue<Muchie> q;
vector<pair<int, int>> sol;
int n, m, cost;
bool in_apm[NMAX];

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

void prim()
{
    in_apm[1] = 1;
    for(auto vec: G[1]) q.push({1,vec.nod,vec.cost});

    while(!q.empty()) {
        auto top = q.top();
        q.pop();
        int nod = top.to;
        if(in_apm[nod])
            continue;

        in_apm[nod] = 1;
        sol.push_back({top.from, top.to});
        cost += top.cost;

        for(auto vec: G[nod]) {
            if(!in_apm[vec.nod]) q.push({nod, vec.nod, vec.cost});
        }
    }
}

void afisare()
{
    fout<<cost<<'\n';
    fout<<n-1<<'\n';
    for(auto m: sol) {
        fout<<m.first<<' '<<m.second<<'\n';
    }
}

int main()
{
    read();
    prim();
    afisare();
    return 0;
}