#include <bits/stdc++.h>

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

//#define fin std::cin 
//#define fout std::cout 

const int nmax = 2e3 + 5;
const int inf = 1e9;

int n, m;
int cost[nmax][nmax];
bool visited[nmax];
int min_cost[nmax], father[nmax];
int MST_cost;
std::vector<std::pair<int, int>> edges;

void prim(int root)
{
    for(int i = 1; i <= n; ++i)
    {
        min_cost[i] = inf;
        father[i] = -1;
    }

    min_cost[root] = 0;

    for(int i = 1; i <= n; ++i)
    {
        int best = -1;
        int min_node = inf;

        for(int j = 1; j <= n; ++j)
            if(!visited[j] && min_cost[j] < min_node)
            {
                min_node = min_cost[j];
                best = j;
            }
        
        visited[best] = true;
        MST_cost += min_cost[best];

        if(father[best] != -1)
            edges.push_back({father[best], best});

        for(int j = 1; j <= n; ++j)
            if(!visited[j] && min_cost[j] > cost[best][j])
            {
                min_cost[j] = cost[best][j];
                father[j] = best;
            }
    }
}

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

    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            cost[i][j] = inf;

    for(int i = 1; i <= m; ++i)
    {
        int x, y, c;
        fin >> x >> y >> c;
        cost[x][y] = cost[y][x] = c;
    }

    prim(1);

    fout << MST_cost << "\n" << n - 1 << "\n";
    for(auto edge : edges)
        fout << edge.first << " " << edge.second << "\n";

    return 0;
}