#include <bits/stdc++.h>
#define NMAX 200000

using namespace std;

int N,M;
long long sum = 0;

struct muchii
{
    int nod1, nod2, cost;
};

vector<muchii> vecin[NMAX + 5];
vector<muchii> sol;

struct cmp
{
    bool operator()(const muchii &a, const muchii &b)
    {
        return a.cost > b.cost; /// asta sorteaza crescator dupa cost, fix invers decat se pune semnul
    }
};

void initArray(bool pus[])
{
    for(int i = 1; i <= N; i++)
    {
        pus[i] = 0;
    }
}

void addNeighbours(int node, priority_queue<muchii, vector<muchii>, cmp> &pq, bool pus[])
{
    for(auto it : vecin[node])
    {
        if(pus[it.nod1] == 0)
        {
             pq.push(it);
        }
    }
}

void Prim()
{
    bool pus[NMAX + 5];
    initArray(pus);

    priority_queue<muchii, vector<muchii>, cmp> pq;
    int start = 1; /// nodul de start e aleator
    pus[start] = 1;

    /// in pq am mereu optiunile de muchii pe care ma pot duce in acel moment (adica vecinii nodurilor din apm)
    addNeighbours(start, pq, pus);

    while(pq.empty() == 0)
    {
        muchii bestNode = pq.top();
        pq.pop();
        /// iau nodul vecin cel mai bun ca si cost

        /// verific daca il am in apm
        if(pus[bestNode.nod1] == 1)
        {
            continue;
        }
        pus[bestNode.nod1] = 1; /// il pun in apm
        sum += bestNode.cost;
        sol.push_back(bestNode);

        /// ii adaug vecinii
        addNeighbours(bestNode.nod1, pq, pus);

    }

}

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

    int n1, n2, c;

    cin>>N>>M;
    for(int i = 1; i <= M; i++)
    {
        cin >> n1 >> n2 >> c;
        vecin[n1].push_back({n2, n1, c});
        vecin[n2].push_back({n1, n2, c});
    }
    Prim();

    cout<<sum<<'\n'<<sol.size()<<'\n';
    for(auto it:sol)
    {
        cout<<it.nod1<<' '<<it.nod2<<'\n';
    }
    return 0;
}