#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct muchie
{
    int x,y,cost;
};
struct cmp
{
    bool operator()(muchie a,muchie b)
    {
        return a.cost>b.cost;
    }
};
bool viz[200005];
vector<muchie> v[200005];
vector<muchie> sol;
priority_queue<muchie,vector<muchie>,cmp>heap;
int n,m,sum;
int main()
{
    f>>n>>m;
    for(int i=0;i<m;i++)
    {
        int x,y,z;
        f>>x>>y>>z;
        v[x].push_back({x,y,z});
        v[y].push_back({y,x,z});
    }
    int nrnod=1;
    for(auto i:v[1])
    {
        heap.push(i);
    }
    viz[1]=true;
    while(nrnod<n)
    {
        auto i=heap.top();
        heap.pop();
        if(!viz[i.y])
        {
            viz[i.y]=true;
            for(auto j:v[i.y])
                heap.push(j);
            sol.push_back(i);
            sum+=i.cost;
            nrnod++;
        }
    }
    g<<sum<<"\n";
    g<<sol.size()<<"\n";
    for(int i=0;i<sol.size();i++)
    {
        g<<sol[i].x<<" "<<sol[i].y<<"\n";
    }
    return 0;
}