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

using namespace std;

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()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    scanf("%d %d", &N, &M);
    for (i=1; i<=M; i++)
    {
        scanf("%d %d %d", &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});
    for (j=1; j<=N; j++)
    {
        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];
    printf("%d\n%d\n", SUM, N-1);
    for (i=1; i<=N; i++)
    {
        if (FAT[i]==0)
            continue;
        printf("%d %d\n", FAT[i], i);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}