#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

struct nod{

    int x,y,c;
    bool operator<(const nod& other) const {
        return c > other.c;

    }
};

priority_queue<nod> q;
vector< pair <int,int >> gr[200005],sol;

bool fol[200005];
int n,m,costmin,nr;

void citire()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        f>>x>>y>>c;
        gr[x].push_back({y,c});
        gr[y].push_back({x,c});
    }
}



void rezolv()
{
    fol[1]=1;
    for(const auto& it:gr[1])
        q.push({1,it.first,it.second});
    while(!q.empty())
    {
        nod nd=q.top();
        int x=nd.x,y=nd.y;
        q.pop();
        if(fol[x]==1 && fol[y]==1)
            continue;
        costmin+=nd.c;
        sol.push_back({x,y});
        if(fol[x]==0)
            y=x;
        fol[y]=1;
        nr++;
        if(nr==m-1)
            break;
        for(const auto &it:gr[y])
            if(fol[it.first]==0)
        q.push({y,it.first,it.second});

    }

}

int main()
{
    citire();
    rezolv();
    g<<costmin<<endl<<nr<<endl;
    for (const auto& it: sol)
        g<<it.first<<' '<<it.second<<endl;
    return 0;
}