#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define nmax 200001
#define INF 999999999

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

vector <pair<int, int> > v[nmax];
vector <pair<int, int> > mfinale;
priority_queue <pair<int, pair<int, int> > > myheap;

int main()
{
    int N, M, x, y, cost;
    f>>N>>M;

    vector <int> dist(N, nmax);
    vector <int> viz(N);

    for (int i = 1; i <= M; i++)
    {
        f>>x>>y>>cost;
        v[x].push_back(make_pair(cost, y));
        v[y].push_back(make_pair(cost, x));
    }
    cost = 0;

    for (int i = 0; i < (int)v[2].size(); i++)
    {
        pair <int, int> it = v[2][i];
        pair <int, pair<int, int> > muchie = make_pair(-it.first, make_pair(2, it.second));
        myheap.push(muchie);
    }

    viz[2] = 1;

    while (!myheap.empty())
    {
        pair <int, pair<int, int> > it = myheap.top();
        int index = it.second.second;
        myheap.pop();
        if (viz[index] == 1){

            continue;
        }
        viz[index] = 1;

        cost -= it.first;
        //cout<<it.second.first<<" "<<it.second.second<<" "<<-it.first<<"   "<<cost<<"\n";
        mfinale.push_back(it.second);

        for (int i = 0; i < (int)v[index].size(); i++)
        {
            pair <int, int> it2 = v[index][i];
            pair <int, pair<int, int> > muchie = make_pair(-it2.first, make_pair(index, it2.second));
            if (viz[muchie.second.second] == 0)
                myheap.push(muchie);
            //else
             //   cout<<it.second.first<<" "<<it.second.second<<" "<<-it.first<<"\n";
        }
    }

    g<<cost<<"\n";
    g<<N-1<<"\n";
    for (int i = 0; i < (int)mfinale.size(); i++)
        g<<mfinale[i].first<<" "<<mfinale[i].second<<"\n";

    return 0;
}