#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int LMAX = 1005;
const int INF = 0x3F3F3F3F;

vector<pair<int, int>> L[LMAX];
vector<pair<int, int>> marb;
bool inTree[LMAX];
int dist[LMAX];

int main()
{   int n, c, i, j, x, y, m;
    fin>>n>>m;
    for (i = 1; i <= m; i++) {
        fin>>x>>y>>c;
        L[x].push_back({y, c});
        L[y].push_back({x, c});
    }
    int s = 0;
    for (i = 1; i <= n; i++) {
        dist[i] = INF;
    }
    inTree[1] = 1;
    dist[1] = 0;
    for (pair<int, int> vec : L[1]) {
        dist[vec.first] = min(dist[vec.first], vec.second);
    }
    for (i = 2; i <= n; i++) {
        int u = 0, mini = INF;
        for (j = 1; j <= n; j++) {
            if (!inTree[j] && dist[j] < mini) {
                mini = dist[j];
                u = j;
            }
        }
        for (pair<int, int> vec : L[u]) {
            if (inTree[vec.first] && vec.second == mini) {
                s += mini;
                inTree[u] = 1;
                marb.push_back({vec.first, u});
                for (pair<int, int> x : L[u]) {
                    dist[x.first] = min(dist[x.first], x.second);
                }
                break;
            }
        }
    }
    fout<<s<<"\n"s;
    fout<<n-1<<"\n";
    for (i = 0; i < n - 1; i++) fout<<marb[i].first<<" "<<marb[i].second<<"\n";




    fin.close();
    fout.close();
    return 0;
}