#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define p pair<int,int>


using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");


struct s{
    int from, to, cost;
};

class comparatie
{
public:
    bool operator () (const s a, const s b)
    {
        return a.cost>b.cost;
    }
};

int n, m, from, to , cost, viz[200005];
priority_queue<s,vector<s>,comparatie>q;
vector<p>graph[200005];
vector<p>sol;

void citire()
{
    f >> n >> m;
    for (int c=0; c<m; c++)
    {
        f >> from >> to >> cost;
        graph[from].push_back({to,cost});
        graph[to].push_back({from,cost});
    }
}

void rezolvare()
{
    int k=1, suma=0, anterior=1;
    viz[1]=1;
    for (auto &v:graph[1])
    {
       q.push({1,v.first,v.second});
    }
    while (k<n)
    {
        s element=q.top();
        q.pop();
        if (viz[element.to]==0)
        {
            suma+=element.cost;
            k++;
            viz[element.to]=1;
            sol.push_back({element.from,element.to});

            for (auto &v:graph[element.to])
            {
                if (viz[v.first]==0)
                q.push({element.to,v.first,v.second});
            }
        }
    }
    g << suma << '\n' <<n-1 <<'\n';
    for (auto &v:sol)
    {
        g << v.first <<' ' << v.second << '\n';
    }
}

int main() {
    citire();
    rezolvare();
    return 0;
}