#include <bits/stdc++.h>
using namespace std;

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

struct compare{
    bool operator()(tuple<int,int,int> l, tuple<int,int,int> r)
    {
        return get<2>(l) > get<2>(r);
    }
};


const int N = 200'002;

vector<pair<int, int>> gr[N];
priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, compare> q;
int n, m, x, y, z, wght, daddies_uwu[N]; // oh nooo, cringeeee, imi pare rau de cn citeste asta
bool vis[N];

void prim(int k)
{
    q.push({0, k, 0});
    while (!q.empty())
    {
        int nodt = get<0>(q.top());
        int nod = get<1>(q.top());
        int cost = get<2>(q.top());
        q.pop();
        if (vis[nod] == 1) continue;
        vis[nod] = 1;
        daddies_uwu[nod] = nodt;
        wght += cost;
        for (auto i: gr[nod])
        {
            if(vis[i.first] == 0)
            {
                q.push({nod, i.first, i.second});
            }
        }
    }
}

int main()
{
    fin>>n>>m;
    for (int i = 1; i <= m; i ++)
    {
        fin>>x>>y>>z;
        gr[x].push_back({y, z});
        gr[y].push_back({x, z});
    }
    prim(1);
    fout<<wght<<"\n"<<n - 1<<"\n";
    for(int i = 2; i <= n; i++)
    {
        fout<<daddies_uwu[i]<<" "<<i<<"\n";
    }
}