#include <bitset>
#include <cstdio>
#include <vector>
#include <queue>

#define NMAX 200005

using namespace std;

vector <pair<int,int > >sol;
vector <pair<int,int > >v[NMAX];

bitset <NMAX>ap;
priority_queue <pair <int ,pair <int ,int > > >q;

int n,m,x,y,z,distanta;

inline void extindere(int nod){
   for (auto it:v[nod])
     if (!ap[it.first])q.push(make_pair(-it.second,make_pair(nod,it.first)));
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

    scanf("%d %d\n",&n,&m);
    for (;m;m--){
        scanf("%d %d %d\n",&x,&y,&z);
        v[x].push_back(make_pair(y,z));
        v[y].push_back(make_pair(x,z));
    }
    ap[1]=1;
    extindere(1);

    while (!q.empty() && sol.size()<n){
       int nodd=q.top().second.second;
       int nods=q.top().second.first;
       int dist=-q.top().first;
       q.pop();

       if (ap[nodd])continue;

       ap[nodd]=1;
       distanta+=dist;
       sol.push_back(make_pair(nods,nodd));
       extindere(nodd);
    }
    printf("%d\n%d\n",distanta,sol.size());
    for (auto it:sol)printf("%d %d\n",it.first,it.second);

    fclose(stdin);
    fclose(stdout);
}