#include <bits/stdc++.h>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

int graph[1005][1005];
int n, m, cmin, x, y, c;
vector<pair<int,int>> ans;
int parent[1005];
int key[1005];
bool mstSet[1005];

int minKey(int key[], bool mstSet[])
{
    int Min = INT_MAX;
    int min_index = 0;
    for (int v = 0; v < n; v++)
        if (mstSet[v] == false & key[v] <  Min)
            Min = key[v], min_index = v;

    return min_index;
}

void printMST(int parent[], int graph[1005][1005])
{
    for (int i = 1; i < n; i++) {
        ans.push_back({parent[i] + 1, i + 1});
        cmin += graph[i][parent[i]];
    }
}

void primMST(int graph[1005][1005])
{

    for (int i = 0; i < n; i++)
        key[i] = INT_MAX, mstSet[i] = false;

    key[0] = 0;
    parent[0] = -1;

    for (int count = 0; count < n - 1; count++) {
        int u = minKey(key, mstSet);
        mstSet[u] = true;

        for (int v = 0; v < n; v++)
            if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
                parent[v] = u, key[v] = graph[u][v];
    }
    printMST(parent, graph);
}

int main()
{
    in>>n>>m;

    for (int i = 1; i <= m; i++) {
        in>>x>>y>>c;
        graph[x - 1][y - 1] = c;
        graph[y - 1][x - 1] = c;
    }

    primMST(graph);

    out<<cmin<<'\n';
    out<<n - 1<<'\n';
    for(auto it:ans)
        out<<it.first<<" "<<it.second<<'\n';
    return 0;
}