#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
FILE*in=fopen("apm.in","r");
FILE*out=fopen("apm.out","w");
const int NMAX=200007;
int n,m,x,y,c,i,s;
bool b[NMAX];
struct edge
{
    int dad,nod,cost;
};
edge f,g;
vector<edge> adj[NMAX];
vector<int> mx,my;
priority_queue<edge> pq;
inline bool operator<(edge a, edge b)
{
    return a.cost>b.cost;
}
void alg()
{
    while(!pq.empty())
    {
        f=pq.top();
        pq.pop();
        if(b[f.nod]==1)
        {
            continue;
        }
        s+=f.cost;
        b[f.nod]=1;
        mx.push_back(f.dad);
        my.push_back(f.nod);
        for(auto w:adj[f.nod])
        {
            pq.push(w);
        }
    }
}
int main()
{
    fscanf(in,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(in,"%d%d%d",&x,&y,&c);
        f.dad=x;
        f.cost=c;
        f.nod=y;
        adj[x].push_back(f);
        f.nod=x;
        f.dad=y;
        adj[y].push_back(f);
    }
    b[1]=1;
    for(auto w:adj[1])
    {
        pq.push(w);
    }
    alg();
    fprintf(out,"%d\n%d\n",s,n-1);
    for(i=0;i<n-1;i++)
    {
        fprintf(out,"%d %d\n",mx[i],my[i]);
    }
}