#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 = 1e5 + 5;
const int inf = 1e9;

int n, m;
std::vector<std::pair<int, int>> graph[nmax];
bool visited[nmax];
int dist[nmax];
int MST_cost;
std::vector<std::pair<int, int>> edges;

void prim(int root)
{
    std::priority_queue<std::pair<int, std::pair<int, int>>, 
        std::vector<std::pair<int, std::pair<int, int>>>,
        std::greater<std::pair<int, std::pair<int, int>>>> q;

    q.push({0, {0, root}});

    while(!q.empty())
    {
        int src = q.top().second.first;
        int dest = q.top().second.second;
        int cost = q.top().first;
        q.pop();

        if(visited[dest])
            continue;
        visited[dest] = true;

        if(src != 0)
            edges.push_back({src, dest});

        MST_cost += cost;

        for(auto edge : graph[dest])
        {
            int adj = edge.first;
            int new_cost = edge.second;

            if(!visited[adj])
                q.push({new_cost, {dest, adj}});
        }
    }
}

int main() 
{
    fin >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        int x, y, c;
        fin >> x >> y >> c;
        graph[x].push_back({y, c});
        graph[y].push_back({x, c});
    }

    prim(1);

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

    return 0;
}