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

ifstream fin("apm.in");
ofstream fout("apm.out");

vector<vector<pair<int, int>>> graf;
vector<tuple<int, int, int>> apcm;
vector<int> viz;
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;

int N, M;

void prim(int x, int& nr, int& s)
{
    viz[x] = 1;

    for(auto& vec : graf[x])
    {
        int ad = vec.first;
        int cost = vec.second;

        if(viz[ad] == 0)
            pq.push({cost, x, ad});
    }

    while(!pq.empty())
    {
        /// iau muchia cu costul minim
        tuple<int, int, int> mcm = pq.top();
        pq.pop();

        /// construiesc apcm
        int cost, v1, v2;
        cost = get<0>(mcm);
        v1 = get<1>(mcm);
        v2 = get<2>(mcm);

        if(viz[v2] == 0)
        {
            apcm.push_back({v1, v2, cost});
            nr++;
            s+=cost;
        }

        viz[v2] = 1;

        if(nr == N-1)
            return ;

        for(auto& vec : graf[v2])
        {
            int cost, ad;
            ad = vec.first;
            cost = vec.second;

            if(viz[ad] == 0)
                pq.push({cost, v2, ad});
        }
    }

}

int main()
{
    fin>>N>>M;
    viz.assign(N+1, 0);
    graf.resize(N+1);
    for(int i=1; i<=M; i++)
    {
        int X, Y, C;
        fin>>X>>Y>>C;
        graf[X].push_back({Y,C});
        graf[Y].push_back({X,C});
    }

    int nr = 0; /// cate muchii am in apcm
    int s = 0;

    prim(1, nr, s);

    fout<<s<<endl<<nr<<endl;

    for(int i=0; i<nr; i++)
    {
        int v1 = get<0>(apcm[i]);
        int v2 = get<1>(apcm[i]);
        fout << v1 << ' ' << v2 << endl;
    }

    return 0;
}