#include <bits/stdc++.h>

using namespace std;

const int inf = 2001;

vector <pair <int, int> > A[200010];
vector <pair <int, int> > arb;
int d[200010];
int nod[200010];

bool viz[200010];

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

int n, m;

int main()
{
    f >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, y, c;
        f >> x >> y >> c;
       // cout << x << y << c << "\n";
        A[x].push_back(make_pair(y ,c));
        A[y].push_back(make_pair(x, c));
    }

    for (int i = 1; i <= n; i++) d[i] = inf;
    d[1] = 0;
    viz[1] = true;
    for (auto it : A[1]) {
        nod[it.first] = 1;
        d[it.first] = it.second;
        //cout << it.first << " " << it.second << "\n";
    }
    int cost = 0;
    for (int i = 2; i <= n; i++)
    {
        int minCost = inf;
        int curentNod;
        for (int j = 1; j <= n; j++) {
            if (minCost > d[j] && !viz[j])
            {
                minCost = d[j];
                curentNod = j;
            }
        }
        cost += minCost;
        viz[curentNod] = true;
        arb.push_back(make_pair(nod[curentNod], curentNod) );
        for (auto it : A[curentNod]) {
            if (d[it.first] > it.second) {
                d[it.first] = it.second;
                nod[it.first] = curentNod;
            }
        }
    }
    g << cost << "\n" << n - 1 << "\n";

    for (auto it : arb) {
        g << it.first << " " << it.second << "\n";
    }

    return 0 ;
}