#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#include <queue>
using namespace std;

struct muchie
{
    int cost,x,y;
};

struct CompareCost {
    bool operator()(muchie m1, muchie m2)
    {
        return m1.cost > m2.cost;
    }
};

vector<pair<int,int>> prim(vector <vector<muchie>> &muchii,int &cost)
{
    priority_queue<muchie,vector<muchie>,CompareCost> q;
    vector<bool> visited(muchii.size(),false);
    vector<pair<int,int>> rez;
    muchie aux;
    aux.x = 1;
    aux.y = 1;
    aux.cost = 0;
    q.push(aux);
    visited[1] == true;
    cost = 0;
    while (q.size() != 0)
    {
        muchie aux = q.top();
        q.pop();
        if (aux.x != aux.y && visited[aux.y] == false)
        {
            rez.push_back({aux.x,aux.y});
            cost = cost + aux.cost;
        }
        visited[aux.x] = true, visited[aux.y] = true;
        for (int i = 0; i < muchii[aux.y].size(); i++)
        {
            muchie m = muchii[aux.y][i];
            if(visited[m.y] == false)
            {
                q.push(m);
            }
        }
    }
    return rez;
}

int main()
{
    ifstream in("apm.in");
    ofstream out("apm.out");

    int n,m;
    in >> n >> m;
    vector<vector<muchie>> muchii(n+1);
    for (int i = 0; i < m; i++)
    {
        int x,y,c;
        in >> x >> y >> c;
        muchie aux;
        aux.x = x;
        aux.y = y;
        aux.cost = c;
        muchii[x].push_back(aux);
        aux.y = x;
        aux.x = y;
        muchii[y].push_back(aux);
    }
    int cost;
    vector<pair<int,int>> rez;
    rez = prim(muchii,cost);
    out << cost << "\n" << rez.size() << "\n";
    for (int i = 0; i < rez.size(); i++)
    {
        out << rez[i].first << " " << rez[i].second << "\n";
    }
    

    in.close();
    out.close();
    return 0;
}