#include <stdio.h>
#include <vector>
#include <queue>
#define mp make_pair
#define s second
#define f first
using namespace std;
int i,x,y,z,n,m;
int cost,t[200005];
vector <pair <int, int> > v[200005],sol;
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(make_pair(z,y));
    v[y].push_back(make_pair(z,x));

}
h.push(mp(0,mp(1,1)));
//t[1]=0;
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;
   h.pop();
   for(i=0;i<v[nod].size();i++)
    {if(!t[v[nod][i].s]){
    //t[v[nod][i].s]=nod;
    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=0;i<sol.size();i++){
    printf("%d %d\n",sol[i].f,sol[i].s);

}



       return 0;
}