#include <fstream>
#include <vector>
#include <queue>

/**
 Algoritmul lui Prim - Jarnick
*/

using namespace std;

const int NMAX = 200001,
          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];
/**
  T[i] = tatal lui i
  D[i] = costul minim al unei muchii având o extremitate i
         și o extremitate în arbore
*/
bool viz[NMAX]; ///viz[i] = 1 <=> nodul i a fost selectat

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 nealese = N;
    while(nealese)
    {
        int x = 0; ///(*)
        while(viz[x])
        {
            x = Q.top().first;
            Q.pop();
        }
        viz[x] = true;
        COST += D[x];
        nealese--;
        for(unsigned i = 0; i < G[x].size(); ++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; ///artificiu (*)
    Prim();
    afisare();
    return 0;
}