#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#define DIMN 200001

using namespace std;
vector <pair <int,int> > v[DIMN];
pair <int,int> w[DIMN];
priority_queue <pair <int,pair <int,int> > > h;
int f[DIMN];
int main()
{
    FILE *fin=fopen ("apm.in","r");
    FILE *fout=fopen ("apm.out","w");
    int n,m,i,x,y,c,sum,sol;
    fscanf (fin,"%d%d",&n,&m);
    for (i=1;i<=m;i++){
        fscanf (fin,"%d%d%d",&x,&y,&c);
        v[x].push_back(make_pair(y,c));
        v[y].push_back(make_pair(x,c));
    }
    for (i=0;i<v[1].size();i++)
        h.push(make_pair(-v[1][i].second,make_pair(v[1][i].first,1)));
    f[1]=1;
    sum=0;
    sol=0;
    while (!h.empty()){
        c=-h.top().first;
        y=h.top().second.first;
        x=h.top().second.second;
        h.pop();
        while (!h.empty() && f[y]){
            c=-h.top().first;
            y=h.top().second.first;
            x=h.top().second.second;
            h.pop();
        }
        if (h.empty())
            break;
        /// avem o muchie de luat in considerare
        sum+=c;
        w[++sol]=make_pair(x,y);
        f[y]=1;
        for (i=0;i<v[y].size();i++){
            if (!f[v[y][i].first])
                h.push(make_pair(-v[y][i].second,make_pair(v[y][i].first,y)));
        }
    }
    fprintf (fout,"%d\n%d\n",sum,sol);
    for (i=1;i<=sol;i++)
        fprintf (fout,"%d %d\n",w[i].first,w[i].second);
    return 0;
}