#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

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

int n,m,x,y,price,i,vf,val_varf_min,cost_total,cost[200001],tata[200001];
vector <pair <int,int> > v[200001];
bitset <200001> trecut;

void set_toINF()
{
    for(i = 1; i <= n; ++ i)
        cost[i] = INF;
}
void aflu_min()
{
    val_varf_min = INF;
    for(i = 2; i <= n; ++ i)
        if(!trecut[i] && cost[i] < val_varf_min)
        {
            val_varf_min = cost[i];
            vf = i;
        }
}
int totalCost()
{
    int total_cost = 0;
    for(i = 2; i <= n; ++ i)
        total_cost += cost[i];
    return total_cost;
}
int main()
{
    {
        // Citire
        f >> n >> m;
        while(m --)
        {
            f >> x >> y >> price;
            v[x].push_back({y,price});
            v[y].push_back({x,price});
        }
    }
    {
        //Initializare
        set_toINF();
        cost[1] = 0;
        trecut[1] = 1;
        for(i = 0; i < v[1].size(); ++ i)
        {
            cost[v[1][i].first] = v[1][i].second;
            tata[v[1][i].first] = 1;
            cost_total += v[1][i].second;
        }
    }
    {
        //Algoritm
        for(int pasi = 1; pasi < n; ++ pasi)
        {
            aflu_min();
            trecut[vf] = 1;
            for(i = 0; i < v[vf].size(); ++ i)
                if(!trecut[v[vf][i].first])
                {
                    if(cost[v[vf][i].first] == INF)
                    {
                        cost_total += v[vf][i].second;
                        cost[v[vf][i].first] = v[vf][i].second;
                        tata[v[vf][i].first] = vf;
                    }
                    else if(v[vf][i].second < cost[v[vf][i].first])
                    {
                        cost_total -= cost[v[vf][i].first] - v[vf][i].second;
                        cost[v[vf][i].first] = v[vf][i].second;
                        tata[v[vf][i].first] = vf;
                    }
                }
        }
    }
    {
        // Afisare
        g << cost_total << '\n' << n - 1;
        for(i = 2; i <= n; ++ i)
            g << '\n' << tata[i] << ' ' << i;
    }
    /// Adaug costul initial si il modific pe parcurs
    /// Pun ca tata de inceput 1, in caz ca tatii alora nu se modifica si altfel ar ramane 0
    /// Daca e costul INF, modific cu drumul, daca nu, cu minimul dintre drumul dinainte si cel de acum
}