#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
vector<vector<pair<int,int>>> graf;
vector<int> visited;
vector<pair<int,int>> apmEdges;
int apmCost;
int n, m;
ifstream in("apm.in");
ofstream out("apm.out");
struct Edge
{
    int from;
    int to;
    int cost;
    Edge(int _x, int _y, int _c) : from(_x), to(_y), cost(_c){

    }
    Edge(const Edge& e) : from(e.from), to(e.to), cost(e.cost){

    }
    bool operator<(const Edge& e) const
    {
        if (cost == e.cost)
            if (from == e.from)
                return to > e.to;
            else
                return from > e.from;
        else
            return cost > e.cost;
    }
};
void primAlg()
{
    priority_queue<Edge> q;
    for (int i = 0; i < graf[1].size(); i++)
        q.push(Edge(1, graf[1][i].first, graf[1][i].second));
    int added = 0;
    visited[1] = 1;
    while (added < n - 1)
    {
        Edge cur = q.top();
        q.pop();
        if (visited[cur.to])
            continue;
            
        apmEdges.push_back(make_pair(cur.from, cur.to));
        added++;
        apmCost += cur.cost;

        visited[cur.to] = 1;
        for (int i = 0; i < graf[cur.to].size(); i++)
        {
            int neighbour = graf[cur.to][i].first;
            int cost = graf[cur.to][i].second;
            if (!visited[neighbour])
            {
                q.push(Edge(cur.to, neighbour, cost));
            }
        }

    }

}
void afisare()
{
    out << apmCost << "\n" << apmEdges.size() << "\n";
    for (int i = 0; i < apmEdges.size(); i++)
        out << apmEdges[i].first << " " << apmEdges[i].second << "\n";
    
}
int main()
{
    in >> n >> m;
    int x,y,c;
    apmCost = 0;
    graf.resize(n+1);
    visited.resize(n+1, 0);
    for (int i = 0; i < m; i++)
    {
        in >> x >> y >> c;
        graf[x].push_back(make_pair(y,c));
        graf[y].push_back(make_pair(x,c));
    }

    primAlg();
    afisare();
    

}