#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

const int MAX=1e5;
int n,i,m,nod1,nod2,cost;
long long sum;
bool viz[MAX+5];
vector <pair<int,int>> muchii[MAX+5],sol;

class Compare{
    public:
    bool operator () (tuple<int,int,int> a, tuple<int,int,int> b)
    {
        return get<2>(a)>get<2>(b);
    }
};

priority_queue <tuple<int,int,int>, vector<tuple<int,int,int>>, Compare> pq;



void add(int nod)
{
    viz[nod]=1;
    for (auto x: muchii[nod])
    {
        int nod2=x.first,cost=x.second;

        if (!viz[nod2])
            pq.push({nod,nod2,cost});
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    fin>>n>>m;
    while (m--)
    {
        fin>>nod1>>nod2>>cost;
        muchii[nod1].push_back({nod2,cost});
        muchii[nod2].push_back({nod1,cost});
    }

    add(1);

    while (!pq.empty())
    {
        nod1=get<0>(pq.top()); nod2=get<1>(pq.top()); cost=get<2>(pq.top());
        pq.pop();

        if (viz[nod2])
            continue;

        sum+=cost;
        sol.push_back({nod1,nod2});
        add(nod2);
    }



    fout<<sum<<"\n"<<sol.size()<<"\n";
    for (auto x: sol)
        fout<<x.first<<" "<<x.second<<"\n";
    return 0;
}