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


using namespace std;

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

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

int n, m, from, to , cost, viz[200005];
priority_queue<p,vector<p>,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(v);
    }
    while (k<n)
    {
        p element=q.top();
        q.pop();
        if (viz[element.first]==0)
        {
            suma+=element.second;
            k++;
            viz[element.first]=1;
            sol.push_back({anterior,element.first});
            anterior=element.first;
            for (auto &v:graph[element.first])
            {
                if (viz[v.first]==0)
                q.push(v);
            }
        }
    }
    g << suma << '\n' <<n-1 <<'\n';
    for (auto &v:sol)
    {
        g << v.first <<' ' << v.second << '\n';
    }
}

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