#include<cstdio>
#include<vector>
#include<set>
#include<bitset>
#define pii pair<int,int>
using namespace std;
const int nmax = 200005;
const int inf = 1<<30;
int n,m,x,y,c,i,cnt,d[nmax],h[nmax],poz[nmax],care[nmax],a[nmax],b[nmax],sol;
vector<pii> v[nmax];
bitset<nmax> viz;
void heapup(int x)
{
    if(x==1) return;
    int f=x/2;
    if(d[h[f]]>d[h[x]])
    {
        swap(h[x],h[f]);
        swap(poz[h[x]],poz[h[f]]);
        heapup(f);
    }
}
void heapdown(int x)
{
    int s=x*2;
    if(s>cnt) return;
    if(s<cnt && d[h[s]]>d[h[s+1]]) s++;
    if(d[h[x]]>d[h[s]])
    {
        swap(h[x],h[s]);
        swap(poz[h[x]],poz[h[s]]);
        heapdown(s);
    }
}
int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(;m;m--)
	{
	    scanf("%d%d%d",&x,&y,&c);
	    v[x].push_back(make_pair(y,c));
	    v[y].push_back(make_pair(x,c));
	}
	for(i=2;i<=n;i++)
	{
	    d[i]=inf;
	    cnt++;
	    h[cnt]=i;
	    poz[i]=cnt;
	}
	viz[1]=1;
	for(vector<pii>::iterator it=v[1].begin();it!=v[1].end();it++)
	{
	    y=it->first; c=it->second;
	    if(c<d[y])
	    {
	        d[y]=c;
	        care[y]=1;
	        heapup(poz[y]);
	    }
	}
	for(i=2;i<=n;i++)
	{
	    x=h[1]; sol+=d[x];
	    a[i-1]=x; b[i-1]=care[x];
	    poz[h[cnt]]=1;
        h[1]=h[cnt];
        cnt--; viz[x]=1;
        heapdown(1);
        for(vector<pii>::iterator it=v[x].begin();it!=v[x].end();it++)
            if(!viz[it->first])
            {
                y=it->first; c=it->second;
                if(c<d[y])
                {
                    d[y]=c;
                    care[y]=x;
                    heapup(poz[y]);
                }
            }
	}
	printf("%d\n%d\n",sol,n-1);
	for(i=1;i<=n-1;i++) printf("%d %d\n",a[i],b[i]);
	return 0;
}