#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int VAL=200005;
const int INF=2000000000;

int N, M, i, j, nod, SUM, NODES;
int A, B, C, FAT[VAL], dist[VAL];
bool viz[VAL];
vector < pair <int ,int> > G[VAL];
vector < pair <int, int> > :: iterator itG;
priority_queue < pair <int, int> > Q;

int main()
{
    fin >> N >> M;
    for (i=1; i<=M; i++)
    {
        fin >> A >> B >> C;
        G[A].push_back({B, C});
        G[B].push_back({A, C});
    }
    for (i=2; i<=N; i++)
    {
        dist[i]=INF;
        Q.push({-INF, i});
    }
    Q.push({0, 1});
    while (1)
    {
        if (NODES==N)
            break;
        if (Q.empty()==true)
            break;
        i=Q.top().second;
        Q.pop();
        if (viz[i]==true)
            continue;
        viz[i]=true;
        NODES++;
        for (itG=G[i].begin(); itG!=G[i].end(); itG++)
        {
            nod=itG->first;
            if (dist[nod]>itG->second && viz[nod]==false)
            {
                dist[nod]=itG->second;
                FAT[nod]=i;
                Q.push({-dist[nod], nod});
            }
        }
    }
    for (i=1; i<=N; i++)
        SUM+=dist[i];
    fout << SUM << '\n';
    fout << N-1 << '\n';
    for (i=1; i<=N; i++)
    {
        if (FAT[i]==0)
            continue;
        fout << FAT[i] << " " << i << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}