#include <cstdio>
#include <vector>
#include <algorithm>
#define maxn 400100
using namespace std;
struct NOD
{
    int x , y , c;
}a[maxn];
int GR[maxn];
int n , m ;
vector <int> V;
bool cmp(NOD A , NOD B)
{
    return(A.c < B.c);
}
int s = 0 ;
int grupa(int i)
{
    if(GR[i] == i)
        return i ;
    GR[i] = grupa(GR[i]);
    return GR[i];
}
void R(int i , int j)
{
    GR[grupa(i)] = grupa(j);
}
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 ",&a[i].x,&a[i].y,&a[i].c);

    }
    for(int i = 1 ; i<=n;++i)
        GR[i] = i;
    sort(a+1,a+m+1,cmp);
    int  k = 0 ;
    for(int i = 1 ; i<=m&&k<n-1;i++)
    {
        if(grupa(a[i].x) != grupa(a[i].y))
        {
            k++;
            s+=a[i].c;
            R(a[i].x,a[i].y);
            V.push_back(i);
        }
    }
    printf("%d\n",s);
    printf("%d\n",n-1);
    for(int i = 0 ; i < V.size();++i)
        printf("%d %d\n",a[V[i]].x,a[V[i]].y);
    return 0;
}