#include<bits/stdc++.h>
#define INF INT_MAX
#define maxN 200005
using namespace std;
int n,m,x,y,c,noduri,minim,seen[maxN],j,sol,da;
pair<int,int> ans[maxN];
vector<pair<int,int> > v[maxN];
int d[maxN],t[maxN];
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,&c);
        v[x].push_back(make_pair(y,c));
        v[y].push_back(make_pair(x,c));
    }
    d[1]=0;
    for(int i=2;i<=n;i++) d[i]=INF;
    noduri=0;
    while(noduri<n)
    {
        minim=INF;
        for(int i=1;i<=n;i++)
        {
            if(!seen[i])
            {
                if(d[i]<minim)
                {
                    minim=d[i];
                    j=i;
                }
            }
        }
        seen[j]=1;
        sol+=d[j];
        if(t[j]) ans[++da]=make_pair(j,t[j]);
        for(vector<pair<int,int> >::iterator it=v[j].begin();it!=v[j].end();it++)
        {
            if((*it).second<d[(*it).first])
            {
                d[(*it).first]=(*it).second;
                t[(*it).first]=j;
            }
        }
        noduri++;
    }
  //  sol=0;
  //  for(int i=1;i<=n;i++) sol+=d[i];
    printf("%d\n",sol);
    printf("%d\n",n-1);
    for(int i=1;i<n;i++) printf("%d %d\n",ans[i].first,ans[i].second);
    return 0;
}