#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

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

struct muchie
{
    int from, to, cost;
    bool operator <(const muchie& a) const
    {
        return cost > a.cost;
    }
};

const int oo = 2e5 + 5;
int n, m, costmin;
vector<muchie> G[oo];
priority_queue<muchie> Q;
bool seen[oo];
vector< pair<int, int> > sol;

void Citire()
{
    fin >> n >> m;
    //G.resize(m);
    for(int i = 1; i <= m; i++)
    {
        int x, y, c;
        fin >> x >> y >>c;
        muchie m;
        m.to = y;
        m.from = x;
        m.cost = c;
        G[x].push_back(m);
        m.to = x;
        m.from = y;
        G[y].push_back(m);
    }

}
void Afisare()
{
    fout << costmin << "\n";
    fout << sol.size() << "\n";
    for(auto i : sol)
        fout << i.first << " " << i.second << "\n";
}

void Prim()
{
    for(auto i : G[1])
        Q.push(i);
    seen[1] = 1;

    while(!Q.empty())
    {
        muchie m = Q.top();
        Q.pop();
        if(!seen[m.to])
        {
            seen[m.to] = true;
            costmin += m.cost;
            sol.push_back({m.from, m.to});
            if(sol.size()==n-1){
                Afisare();
                break ;
            }

            for(auto i : G[m.to])
                if(!seen[i.to])
                    Q.push(i);
        }

    }
}


int main()
{
    Citire();
    Prim();
    return 0;
}