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

#define NMAX 200005

using namespace std;

int n,m,x,y,d;
long long dist;

bitset <NMAX>ap;
vector <pair <int,int > >v[NMAX],sol;
priority_queue <pair<int,pair<int,int > > >q;

int main()
{
   freopen("apm.in","r",stdin);
   freopen("apm.out","w",stdout);
   scanf("%d%d",&n,&m);

   for (int i=1;i<=m;i++)
    {
       scanf("%d%d%d",&x,&y,&d);
       v[x].push_back(make_pair(y,d));
       v[y].push_back(make_pair(x,d));
    }
   for (vector <pair<int,int> >::iterator it=v[1].begin();it!=v[1].end();it++)
     q.push(make_pair(-(*it).second,make_pair(1,(*it).first)));
   ap[1]=1;
   while (q.size() && sol.size()<n-1)
    {
        if (ap[q.top().second.second]){q.pop();continue;}
        int nod=q.top().second.second;
        sol.push_back(make_pair(q.top().second.first,q.top().second.second));
        dist-=q.top().first;
        ap[nod]=1;
        q.pop();
        for (vector <pair<int,int> >::iterator it=v[nod].begin();it!=v[nod].end();it++)
          if (ap[(*it).first]==0)
            q.push(make_pair(-(*it).second,make_pair(nod,(*it).first)));
    }
   printf("%d\n",dist);
   printf("%d\n",n-1);
   for (;sol.size();sol.pop_back())
     printf("%d %d\n",sol.back().first,sol.back().second);

   fclose(stdin);
   fclose(stdout);
}