#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define N_MAX 200010

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

struct a
{
    int x, y;
};
a t[N_MAX];
int n, m, k, s;
vector <pair <int, int> > v[N_MAX];
bool visited[N_MAX];

void read()
{
    in >> n >> m;
    for(int i = 0, a, b, c; i < m; i++)
    {
        in >> a >> b >> c;
        v[a].push_back(make_pair(b, c));
        v[b].push_back(make_pair(a, c));
    }
}

void APM()
{
    priority_queue < pair < int, pair <int, int> >, vector < pair <int, pair<int, int> > >, greater < pair < int, pair <int, int> > > > q;
    q.push(make_pair(0, make_pair(1, 1)));
    k = 1;
    while(k < n)
    {
        int node = q.top().second.second;
        q.pop();
        visited[node] = true;
        for(int i = 0; i < v[node].size(); i++)
        {
            if(!visited[v[node][i].first])
                q.push(make_pair(v[node][i].second, make_pair(node, v[node][i].first)));
        }
        while(visited[q.top().second.second])
            q.pop();
        t[k].x = q.top().second.first;
        t[k++].y = q.top().second.second;
        s += q.top().first;
    }
}

void print()
{
    out << s << '\n' << k - 1 << '\n';
    for(int i = 1; i < k; i++)
        out << t[i].x << " " << t[i].y << '\n';
}

int main()
{
    read();
    APM();
    print();
    return 0;
}