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

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];
bool viz[VAL];
vector < pair <int ,int> > G[VAL];
vector < pair <int, int> > :: iterator itG;
priority_queue < pair <int, int> > Q;

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;
        Q.push({-INF, i});
    }
    Q.push({0, 1});
    while (1)
    {
        if (Q.empty()==true)
            break;
        i=Q.top().second;
        Q.pop();
        if (viz[i]==true)
            continue;
        viz[i]=true;
        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];
    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;
}