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

int main()
{
    ifstream in("apm.in");
    ofstream out ("apm.out");

    if(!in)
    {
        cout << "eroare";
        return -1;
    }
    int n, m;
    in >> n >> m;
    vector <int> viz(n+1);

    for(int i = 0; i < m; ++i)
    {
        int a;
        pair<int, int> vecin;
        in >> a >> vecin.second >> vecin.first;
        vecin.first = -vecin.first;
        graf[a].push_back(vecin);
        graf[vecin.second].push_back({vecin.first, a});
    }

    vector < pair<int,int> > muchii(n);
    int sursa = 1;
    priority_queue < pair<pair<int,int>, int> > q;


    for(pair<int, int> p: graf[sursa])
    {
        q.push({ p, sursa});
    }
    int sum = 0;
    viz[sursa] = 1;
    int index = 0;

    while(!q.empty())
    {
        pair< pair<int, int>, int> mini = q.top();
        q.pop();

        if(viz[mini.first.second] == 1 && viz[mini.second] == 1)
            continue;
        else
        {
            muchii[index++] = {mini.first.second, mini.second};
            sum += -mini.first.first;
            for(pair<int, int> t: graf[mini.first.second])
                if(viz[t.second] == 0)
                    q.push({t, mini.first.second});
            viz[mini.first.second] = 1;

        }
    }
    out << sum << endl;
    out << index << endl;
    for(int i = 0; i < index; ++i)
        out << muchii[i].first << " " << muchii[i].second << endl;

    in.close();
    out.close();
    return 0;
}