#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;
ifstream fin("graf.in");
ofstream fout("graf.out");

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

int N, M;

int prim(int x, int& s, int& nr)
{
    viz[x] = 1;
    nr = 1;
    int curent, parinte, vecin, cost;
    for(auto& vec : graf[x])
    {
        vecin = vec.first;
        cost = vec.second;
        if(viz[vecin] == 0)
        {
            pq.push({cost, x, vecin});
        }
    }

    curent = x;
    tuple<int, int, int> nod;

    while(!pq.empty() && nr<N)
    {
        nod = pq.top();
        pq.pop();
        cost = get<0>(nod);
        parinte = get<1>(nod);
        vecin = get<2>(nod);

        if(viz[vecin] == 0)
        {
            tata[vecin] = {parinte, cost};
            s += cost;
            viz[vecin] = 1;
            nr += 1;
            curent = vecin;
        }

        for(auto& i : graf[curent])
        {
            vecin = i.first;
            cost = i.second;
            if(viz[vecin] == 0)
            {
                pq.push({cost, curent, vecin});
            }
        }
    }
}

int main()
{
    int s= 0, nr = 0;
    fin>>N>>M;
    graf.resize(N+1);
    viz.assign(N+1, 0);
    tata.assign(N+1, {-1,-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 start = 1;

    prim(start, s, nr);

    fout<<s<<endl;
    fout<<nr-1<<endl;
    for(int i=1; i<=N; i++)
    {
        if(tata[i].first != -1)
            fout<<i<<' '<<tata[i].first<<endl;
    }

    return 0;
}