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

#define NMAX 100100
#define INF 9999999

using namespace std;

ifstream f("date.in");
ofstream g("date.out");


vector<pair<int,int> >graf[NMAX];
priority_queue<pair<int,pair<int,int> > > coada;
int n, m, grad[NMAX],tata[NMAX], viz[NMAX];
int costtotal = 0;
void citireGraf()
{
    int x=0,y=0,c=0;
    f>>n>>m;
    for(int i = 0; i < m; i++)
    {
        f>>x>>y>>c;
        graf[x].emplace_back(make_pair(y,c));
        graf[y].emplace_back(make_pair(x,c));
    }
}

void prim(int nodStart)
{
    int lim = graf[nodStart].size();

    for(int i = 0; i < lim; i++)
    {
        int vecin = graf[nodStart][i].first;
        int cost = -graf[nodStart][i].second;
        coada.push({cost,{nodStart,vecin}});

    }

    tata[nodStart] = 0;
    viz[nodStart] = 1;

    while (!coada.empty())
    {
        pair<int,pair<int,int> > best = coada.top();
        coada.pop();

        int sursa = best.second.first;
        int vecin = best.second.second;
        int cost = best.first;

        if(viz[vecin] == 0)
        {
            costtotal += -cost;
            viz[vecin] = 1;
            tata[vecin] = sursa;
            for (int i = 0; i < graf[vecin].size(); i++) {
                coada.push({-graf[vecin][i].second, {vecin, graf[vecin][i].first}});
            }
        }
    }
}

void afisare(int sursa){
    g<<costtotal<<'\n';
    g<<n-1<<'\n';
    for(int i = 1; i <= n; i ++)
    {
        if(i != sursa){

            g<<i<<" "<<tata[i]<<"\n";
        }
    }
}


int main() {

    citireGraf();
    prim(1);
    afisare(1);

    return 0;
}