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

const int NMAX = 200001;
const int INF = 1 << 20;
struct comp
{
    bool operator() (const  pair<int, int> &x, const pair<int, int> &y) const
    {
        return x.second > y.second;
    }
};
priority_queue<pair<int, int>, vector< pair<int, int> >, comp> Q;
vector< pair<int, int> > G[NMAX];

int N, M, COST = 0;
int T[NMAX], D[NMAX];
bool viz[NMAX];
void citire()
{
    ifstream f ("apm.in");
    f >> N >> M;
    int x, y, cost;
    for (int i = 1; i <= M; i++)
    {
        f >> x >> y >> cost;
        G[x].push_back (pair<int, int> (y, cost) );
        G[y].push_back (pair<int, int> (x, cost) );
    }
    f.close();
}
void prim()
{
    int neales = N;
    while (neales)
    {
        int x = 0;
        while (viz[x])
        {
            x = Q.top().first;
            Q.pop();
        }
        viz[x] = true;
        COST += D[x];
        neales--;
        int lg = G[x].size();
        for (int i = 0; i < lg; i++)
            if (G[x][i].second < D[G[x][i].first] && viz[G[x][i].first] == false)
            {
                T[G[x][i].first] = x;
                D[G[x][i].first] = G[x][i].second;
                Q.push (pair<int, int> (G[x][i].first, G[x][i].second) );
            }
    }
}
void afisare()
{
    ofstream g ("apm.out");
    g << COST << '\n' << N - 1 << '\n';
    for (int i = 2; i <= N; i++)
        g << i << ' ' << T[i] << '\n';
    g.close();
}
int main()
{
    citire();
    for (int i = 2; i <= N; i++)
        D[i] = INF;
    Q.push (pair<int, int> (1, 0) );
    viz[0] = true;
    prim();
    afisare();
    return 0;
}