#include <fstream>
#include <vector>
#include <set>

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;
int A, B, C, FAT[VAL], dist[VAL];
vector < pair <int ,int> > G[VAL];
vector < pair <int, int> > :: iterator itG;
set < pair <int, int> > Heap;
set < pair <int, int> > :: iterator itS;

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;
        Heap.insert({INF, i});
    }
    Heap.insert({0, 1});
    while (Heap.size()>0)
    {
        itS=Heap.begin();
        i=itS->second;
        Heap.erase(itS);
        for (itG=G[i].begin(); itG!=G[i].end(); itG++)
        {
            nod=itG->first;
            if (dist[nod]>itG->second)
            {
                itS=Heap.find({dist[nod], nod});
                if (itS==Heap.end())
                    continue;
                Heap.erase(itS);
                dist[nod]=itG->second;
                FAT[nod]=i;
                Heap.insert({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;
}