#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <climits>

FILE *f=fopen("apm.in","r");
FILE *g=fopen("apm.out","w");

#define v first
#define cost second

using namespace std;
const int inf =INT_MAX/2;

struct cmp
{
    bool operator()(const pair<int,int> A,const pair<int,int> B)const
    {
        return A.cost>B.cost;
    }
};

vector<pair<int,int> > lv[200001];
priority_queue<pair<int,int> ,vector<pair<int,int> > ,cmp> Q;

int n,m,k,D[200001],T[200001],viz[200001];

void get_graph()
{
    fscanf(f,"%d%d",&n,&m);
    int a,b,c;
    for(int i=1;i<=m;++i)
    {
        fscanf(f,"%d%d%d",&a,&b,&c);
        lv[a].push_back(make_pair(b,c));
        lv[b].push_back(make_pair(a,c));
    }
}
void prim(int k)
{
    vector<pair<int,int> > ::iterator it;
    for(int i=1;i<=n;++i)D[i]=inf,T[i]=1;
    Q.push(make_pair(1,0));
    D[1]=0;
    int nodc;
    viz[1]=1;
    while(!Q.empty())
    {
        nodc=Q.top().first;Q.pop();
        viz[nodc]=1;
        for(it=lv[nodc].begin();it!=lv[nodc].end();++it)
            if(!viz[it->v]&&D[it->v]>it->cost)
                {
                    D[it->v]=it->cost,T[it->v]=nodc;
                    Q.push(make_pair(it->v,it->cost));
                }
    }
}
int main()
{
    get_graph();
    prim(1);
    int total=0;
    for(int i=1;i<=n;++i)
        total+=D[i];
    fprintf(g,"%d\n%d\n",total,n-1);
    for(int i=2;i<=n;++i)
        fprintf(g,"%d %d\n",i,T[i]);
    return 0;
}