#include <fstream>
#include <algorithm>
#include <queue>
#define ll long long
using namespace std;

const int NMAX = 2e5;

vector <pair <int, int> > g[NMAX + 1];

struct ob
{
    int muchie;
    int nod;
};

bool operator <(ob a, ob b)
{
    return a.muchie > b.muchie;
}

priority_queue <ob> pq;

bool viz[NMAX + 1];

vector <pair <int, int> > sol;

int main()
{
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    int n, m, i;
    cin >> n >> m;
    for (i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }
    int ans = 0;
    int last = 1;
    viz[1] = 1;
    for (i = 1; i <= n; i++)
    {
        for (pair <int, int> x : g[last])
        {
            pq.push({x.second, x.first});
        }
        bool done = 0;
        while (!pq.empty() and !done)
        {
            ob f = pq.top();
            pq.pop();
            if (!viz[f.nod])
            {
                viz[f.nod] = 1;
                sol.push_back({last, f.nod});
                last = f.nod;
                ans += f.muchie;
                done = 1;
            }
        }
    }
    cout << ans << "\n";
    cout << sol.size() << "\n";
    for (pair <int, int> x : sol)
        cout << x.first << " " << x.second << "\n";
}