#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#define mp make_pair
#define f first
#define s second
using namespace std;
int  cost,x,y,z,n,m,i;
int t[200005];
vector <pair <int,int > > sol,v[200005];
priority_queue <pair <int, pair<int,int > > ,vector <pair <int, pair <int, int > > >,greater <pair <int, pair <int, int > > > > h;
int main()
{
   freopen("apm.in","r",stdin);
   freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++) {scanf("%d%d%d",&x,&y,&z);
    v[x].push_back(mp(z,y));
    v[y].push_back(mp(z,x));



    }
   h.push(mp(0,mp(1,1)));
   while(!h.empty()){
        int nod=h.top().s.s;
    if(!t[nod]){
        t[nod]=h.top().s.f;
        sol.push_back(mp(h.top().s.f,nod));
    cost+=h.top().f;
    for(i=0;i<v[nod].size();i++){
        if(!t[v[nod][i].s]) h.push(mp(v[nod][i].f,mp(nod,v[nod][i].s)));

    }

    }
    else h.pop();


   }
   printf("%d\n%d\n",cost,sol.size()-1);
   for(i=1;i<sol.size();i++) printf("%d %d\n",sol[i].f,sol[i].s);
    return 0;
}