# include <fstream>
# include <vector>
# include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct edge{int x,y,w;} e[400001];
int n,m,i,t,c[200001];
vector<pair<int,int> > s;
bool cmp(edge i,edge j)
{
    return(i.w<j.w);
}
void read()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
         {
          f>>e[i].x>>e[i].y>>e[i].w;
          c[e[i].x]=e[i].x;
          c[e[i].y]=e[i].y;
         }
}
int comp(int x)
{
    if(c[x]!=x)
       c[x]=comp(c[x]);
    return c[x];
}
void Kruskal()
{
    int x,y,d=0;
    sort(e+1,e+m+1,cmp);
    n--;
    for(i=1;d<n;i++)
         {
          x=comp(e[i].x);
          y=comp(e[i].y);
          if(x!=y)
             {
              t+=e[i].w;
              s.push_back(make_pair(e[i].x,e[i].y));
              d++;
              c[y]=c[x];
             }
         }
}
void write()
{
    g<<t<<'\n'<<n<<'\n';
    for(i=0;i<n;i++)
          g<<s[i].first<<" "<<s[i].second<<'\n';
}
int main()
{
    read();
    Kruskal();
    write();
    f.close();
    g.close();
    return 0;
}