#include <fstream>
#include <vector>
#include <set>
using namespace std;
ifstream cin ("apm.in");
ofstream cout ("apm.out");
struct ura{
    int nod, cost;
    bool operator <(const ura &other)const{
        return cost < other.cost;
    };
};
multiset <ura> s;
vector <ura> lista[200005];
int cor[200005];
int v[200005];
int used[200005];
void bagapm(int x)
{
    for (int i = 0; i < lista[x].size(); i++)
    {
        int y = lista[x][i].nod;
        int c = lista[x][i].cost;
        if (v[y] > c)
        {
          //  s.erase(s.find({y, v[y]}));
            v[y] = c;
            s.insert(lista[x][i]);
            cor[y] = x;
        }
    }
}
int vc[1005];
struct ura2{
    int x, y;
};
ura2 ans[200005];
int main()
{
    int n, i, j, m, nr;
    cin >> n;
    cin >> m;
    for (i = 1; i <= m; i++)
    {
        int x, y, c;
        cin >> x >> y >> c;
        lista[x].push_back({y, c});
        lista[y].push_back({x, c});
    }
    for (i = 2; i <= n; i++)
        v[i] = 2e9, s.insert({i, v[i]});
    bagapm(1);
    used[1] = 1;
    int cost = 0;
    for (i = 1; i < n; i++)
    {
        int nod = s.begin() -> nod;
        while (used[nod])
        {
            s.erase(s.begin());
            nod = s.begin() -> nod;
        }
        s.erase(s.begin());
        used[nod] = 1;
        bagapm(nod);
        cost += v[nod];
        ans[i] = {nod, cor[nod]};
    }
    cout << cost;
    cout << '\n' << n - 1;
    for (i = 1; i < n; i++)
        cout << '\n' << ans[i].x <<" " << ans[i].y;
    return 0;
}