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

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct nod
{
    int v,cost;
};
int n,m,x,y,c,s,q;
vector <nod> d[200001];
deque <nod> h;
bool viz[200001];
int cost[200001],tata[200001];
void updateHeap(int dim)
{
    int j=dim;
    while(j/2>=1)
        if(h[j].cost<h[j/2].cost)
        {
            swap(h[j/2],h[j]);
            j/=2;
        }
        else
            break;
}
void deleteElemHeap(int dim)
{
    int j=1,j2;
    while(j*2<=dim)
    {
        j2=j*2;
        if(h[j2].cost<h[j].cost)
            j=j2;
        if(j2+1<=dim && h[j2+1].cost<h[j].cost)
            j=j2+1;
        if(j==j2/2)
            break;
        else
            swap(h[j2/2],h[j]);
    }
}
void Prim()
{
    int k=1;
    h.push_front({1,0});
    h.push_front({-1,-1});
    while(k)
    {
        nod i=h[1];
        swap(h[1],h.back());
        h.pop_back();
        k--;
        deleteElemHeap(k);
        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_back({it->v,it->cost});
                k++;
                updateHeap(k);
            }
    }
}
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;
}