#include <fstream>
#include <vector>
#include <queue>
#define CMAX 200000100

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct nod
{
    int v,cost;
};

struct CompareCost {
    bool operator()(const nod& a, const nod& b) {
        return a.cost > b.cost;
    }
};
priority_queue<nod, vector<nod>, CompareCost> h;
int n,m,x,y,c,s,q;
vector <nod> d[200001];
bool viz[200001];
int cost[200001],tata[200001];
void Prim()
{
    int k=1;
    h.push({1,0});
    while(!h.empty())
    {
        nod i=h.top();
        h.pop();
        viz[i.v]=1;
        for(vector <nod>::iterator it=d[i.v].begin(); it!=d[i.v].end(); it++)
            if(it->cost<cost[it->v] && !viz[it->v])
            {
                if(cost[it->v]!=CMAX)
                    s-=cost[it->v];
                s+=it->cost;
                tata[it->v]=i.v;
                cost[it->v]=it->cost;
                h.push({it->v,it->cost});
            }
    }
}
int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        fin>>x>>y>>c;
        d[x].push_back({y,c});
        d[y].push_back({x,c});
    }
    for(int i=2; i<=n; i++)
        cost[i]=CMAX;
    tata[1]=-1;
    Prim();
    tata[1]=0;
    fout<<s<<'\n'<<n-1<<'\n';
    for(int i=2;i<=n;i++)
        fout<<i<<' '<<tata[i]<<'\n';
    return 0;
}