#include <bits/stdc++.h>
 
using namespace std;
 
const int NMAX=2e5+5;
 
int n,m,parent[NMAX],r1[NMAX],r2[NMAX];
vector <pair<int,pair<int,int> > >A;
 
int find(int a)
{
    if(parent[a]==a)
        return a;
    return parent[a]=find(parent[a]);
}
void join(int a, int b)
{
    int x=find(a);
    int y=find(b);
    parent[y]=x;    
}
 
int main()
{
	
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d\n",&n,&m);
     
    for(int i=1;i<=n;i++)
        parent[i]=i;
         
    for(int i=1;i<=m;i++)
    {
        int x,y,w;
        scanf("%d %d %d", &x, &y, &w);
        A.push_back(make_pair(w,make_pair(x,y)));
    }
     
    sort(A.begin(),A.end());
     
    int S=0,nr=0,k=0;
    while(nr<n-1)
    {
        int x=A[k].second.first;
        int y=A[k].second.second;
        int w=A[k].first;
         
        if(find(x)!=find(y))
        {
            join(x,y);
            S+=w;
            nr++;
            r1[nr]=x;
            r2[nr]=y;
        }
        k++;
    }
     
    printf("%d\n",S);
    printf("%d\n",n-1);
    for(int i=1;i<=nr;i++)
        printf("%d %d\n",r1[i],r2[i]);
     
    return 0;
     
}