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

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

struct compare{
    bool operator()(pair<int, int> l, pair <int, int> r)
    {
        return l.second > r.second;
    }
};


const int N = 200'002;

vector<pair<int, int>> gr[N];
priority_queue<pair<int, int>, vector<pair<int,int>>, compare> q;
bool vis[N];
int n, m, x, y, z, edgs = -1, wght;
vector<int> nodes;

void prim(int k)
{
    q.push({k, 0});
    while (!q.empty())
    {
        int nod = q.top().first;
        int cost = q.top().second;
        q.pop();
        if (vis[nod] == 1) continue;
        vis[nod] = 1;
        nodes.push_back(nod);
        edgs++;
        wght += cost;
        for (auto i: gr[nod])
        {
            if(vis[i.first] == 0)
            {
                q.push({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"<<edgs<<"\n";
    for(int i = 0; i < nodes.size() - 1; i++)
    {
        fout<<nodes[i]<<" "<<nodes[i + 1]<<"\n";
    }
}