#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[1].size(); i++)
    {
        pair <int, int> it = v[1][i];
        pair <int, pair<int, int> > muchie = make_pair(-it.first, make_pair(1, it.second));
        myheap.push(muchie);
    }
    viz[1] = 1;

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

        mfinale.push_back(it.second);

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

    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;
}