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

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

struct Edge
{
    int origin;
    int destination;
    int value;

    bool operator< (const Edge& a) const
    {
        return a.value < this->value;
    }
};
int n, m;
priority_queue <Edge> Heap;
vector <Edge> result;
vector <Edge> graph[200005];
bool frv[200005];
long long ans;

void apm()
{
    Heap.push({0,1,0});
 //   frv[1] = true;
    while(!Heap.empty())
    {
        
        while (!Heap.empty() && frv[Heap.top().destination] == true)
        {
            Heap.pop();
        }
        if (Heap.empty())
        {
            break;
        }

        int currNode = Heap.top().destination;
        //cout << currNode << endl;
        ans+= Heap.top().value;
        frv[Heap.top().destination] = true;
        result.push_back(Heap.top());
        Heap.pop();

        for (Edge edge : graph[currNode])
        {
            Heap.push(edge);
        }
    }
}


int main()
{
    fin >> n >> m;
    
    while (m--)
    {
        int a, b, c;
        fin >> a >> b >> c;

        Edge newEdge = {a, b, c};
        graph[a].push_back(newEdge);

        newEdge = {b, a, c};
        graph[b].push_back(newEdge);
    }
    apm();

    fout << ans << '\n';
    fout << result.size() - 1<< '\n';
    for (int i = 1; i < result.size(); i++)
    {
        fout << result[i].origin << ' ' << result[i].destination << '\n';
    }
}