#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <bitset>
#include <cstring>

using namespace std;

const int NMax = 200005;
const int inf = 0x3f3f3f3f;

vector < pair < int, int > > G[NMax];
int N, M;
int cost[NMax], dad[NMax];

priority_queue < pair < int, int > > Q;
bitset < NMax > viz;

void Prim()
{
    Q.push({0,1});
    memset(cost,inf,sizeof(cost));
    cost[1] = 0;

    while(!Q.empty())
    {
        int nod = Q.top().second;
        Q.pop();

        if(viz[nod])
            continue;

        viz[nod] = 1;

        for(auto it: G[nod])
        {
            if(!viz[it.first] && cost[it.first] > it.second)
            {
                cost[it.first] = it.second;
                Q.push({-cost[it.first],it.first});
                dad[it.first] = nod;
            }
        }
    }

    int cst = 0;
    for(int i=2; i<=N; ++i)
            cst += cost[i];

    cout << cst << "\n";
    cout << N-1 << "\n";

    for(int i=2; i<=N; ++i)
        cout << i << " " << dad[i] << "\n";
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    scanf("%d%d",&N,&M);

    for(int i=1; i<=M; ++i)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        G[x].push_back({y,c});
        G[y].push_back({x,c});
    }

    Prim();
    return 0;
}