#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF 200000200
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m;
int ct;
vector <int> Dmin;
vector <int> Tati;
vector <bool> InQ;
vector < pair <int, int> > G[200201];
vector <bool> Selected;

struct Compar
{
    bool operator () (int x, int y)
    {
        return Dmin[x] > Dmin[y];
    }
};
priority_queue < int, vector <int>, Compar > Q;


void Prim()
{
    int i, i_minim;
    vector < pair <int, int> > :: iterator it;

    Q.push(1);

    while(!Q.empty())
    {
        i_minim = Q.top();
        Q.pop();

        Selected[i_minim] = true;
        InQ[i_minim] = false;

        ct += Dmin[i_minim];

        for(it = G[i_minim].begin(); it != G[i_minim].end(); ++it)

            if(!Selected[it -> first] && Dmin[it -> first] > (it -> second))
            {
                Tati[it -> first] = i_minim;
                Dmin[it -> first] = it -> second;

                if(!InQ[it -> first])
                {
                    Q.push(it -> first);
                    InQ[it -> first] = true;
                }
            }
    }

}

int main()
{
    int i, j, x, c;

    fin>>n>>m;

    for(i = 1; i <= m; ++i)
    {
        fin>>x>>j>>c;
        G[x].push_back(make_pair(j, c));
        G[j].push_back(make_pair(x, c));
    }

    Selected.assign(n + 1, false);
    Selected[1] = true;

    Tati.assign(n + 1, 1);
    Tati[1] = 0;

    Dmin.assign(n + 1, INF);
    Dmin[1] = 0;

    InQ.assign(n + 1, false);
    InQ[1] = true;

    Prim();

    fout<<ct<<'\n';
    fout<<n-1<<'\n';
    for(i = 2; i <= n; ++i)
        fout<<i<<' '<<Tati[i]<<'\n';

    return 0;
}