#include <fstream>
#define infinit (1 << 30)
#define nmax 200001
#include <vector>
#include <queue>

using namespace std;

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

int n, m;
int distante[nmax];
bool vizitat[nmax];
int parinte[nmax];

struct cmp
{
    bool operator()(int x,int y)
    {
        return distante[x] > distante[y];
    }
};

priority_queue <int , vector <int > , cmp> coada;
vector <pair < int, int  > > muchii[nmax];

void citeste()
{
    fin >> n >> m;
    for (int i = 1;i <= m; i++)
    {
        int x, y, c;
        fin >>x >> y >> c;
        muchii[x].push_back(make_pair(y,c));
        muchii[y].push_back(make_pair(x,c));
    }
}

void APM(int NodStart)
{
    vizitat[NodStart] = true;
    for (int i = 2; i <= n ;i++)
    {
        distante[i] = infinit;
        parinte[i] = 0;
        coada.push(i);
    }
    distante[NodStart] = 0;
    parinte[NodStart] = -1;
    coada.push(NodStart);
    while (!coada.empty())
    {
        int NodCurent = coada.top();
        coada.pop();
        vizitat[NodCurent] = true;
        for (unsigned int i = 0; i < muchii[NodCurent].size(); i++)
        {
            int vecin = muchii[NodCurent][i].first;
            int cost = muchii[NodCurent][i].second;
            if (cost < distante[vecin] && !vizitat[vecin])
            {
                distante[vecin] = cost;
                parinte[vecin] = NodCurent;
            }
        }
    }

}

void afisare()
{
    int s = 0;
    for (int i = 1; i <= n ;i++)
        {
            if (distante[i] != infinit)
            s += distante[i];
        }
    fout << s << "\n" << n-1 << "\n";
    for (int i = n;i > 1; i--)
        fout << parinte[i] << " " << i << "\n";
}

int main()
{
    citeste();
    APM(1);
    afisare();
    return 0;
}