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

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

int minKey()
{
    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()
{
    for (int i = 1; i < n; i++) {
        ans.push_back({parent[i] + 1, i + 1});
    }
}

void primMST()
{

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

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

    for (int cnt = 0; cnt < n; cnt++) {

        int u = minKey();

        cmin += key[u];
        mstSet[u] = true;
        cout<<cmin<<'\n';
        for (int v = 0; v < n; v++) {
            if (mstSet[v] == false && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }
    printMST();
}

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

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            graph[i][j] = INT_MAX;

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

    primMST();

    out<<cmin<<'\n';
    out<<ans.size()<<'\n';
    int sum = 0;
    for(auto it:ans) {
        sum += graph[it.first - 1][it.second - 1];
        out<<it.first<<" "<<it.second<<'\n';
    }
    out<<sum;
    return 0;
}