#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
FILE*f=fopen("apm.in","r");
FILE*g=fopen("apm.out","w");
priority_queue<pair<int,pair<int,int> >,vector<pair<int,pair<int,int> > >, greater<pair<int,pair<int,int> > > > h;
vector <pair<int,int> > v[200001];
vector <pair<int,int> > sol;
int x,y,c,cost,n,m,t[200001],i;
int main()
{
fscanf(f,"%d%d",&n,&m);
for(i=1;i<=m;i++)
{

    fscanf(f,"%d%d%d",&x,&y,&c);
    v[x].push_back(make_pair(c,y));
    v[y].push_back(make_pair(c,x));
}
h.push(make_pair(0,make_pair(1,1)));
t[1]=0;
while(!h.empty()){
        int nod=h.top().second.second;
    if(t[nod]==0){
        t[h.top().second.second]=h.top().second.first;
        cost+=h.top().first;
        sol.push_back(make_pair(h.top().second.first,nod));
        h.pop();
        for(i=0;i<v[nod].size();i++){
            if(t[v[nod][i].second]==0){
                h.push(make_pair(v[nod][i].first,make_pair(nod,v[nod][i].second)));

            }
        }
    }
    else h.pop();



}
fprintf(g,"%d\n%d\n",cost,sol.size()-1);
for(i=1;i<sol.size();i++){
    fprintf(g,"%d %d\n",sol[i].first,sol[i].second);
}

    return 0;
}