#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int T[100001];
int V[100001][2];
int sef (int x)
{
    if (T[x]!=x)
    T[x]=sef(T[x]);
    return T[x];
}
void join (int x , int y)
{
    int t1=sef(x);
    int t2=sef(y);
    T[t2]=t1;
}
struct muchie
{
    int n1;
    int n2;
    int cost;
};
muchie v[400001];
int sum;
int n1,n2,c;
bool cmp (muchie a , muchie b)
{
    if (a.cost<b.cost)
        return 1;
    return 0;
}
int main()
{
    freopen("apm.in" , "r" , stdin);
    freopen ("apm.out" , "w" , stdout);
    int n,m;
    cin>>n>>m;
    for (int i=1 ; i<=m ; i++)
    {
        cin>>n1>>n2>>c;
        v[i].n1=n1;
        v[i].n2=n2;
        v[i].cost=c;
    }
    for (int i=1 ; i<=n ; i++)
        T[i]=i;
    sort (v+1 , v+m+1 , cmp);
    int cont=0;
    int cont2=0;
    while (cont!=n-1)
    {
        cont2++;
        if (sef(v[cont2].n1)!=sef(v[cont2].n2))
        {
            join (v[cont2].n1 , v[cont2].n2);
            sum+=v[cont2].cost;
            V[cont][1]=v[cont2].n1;
            V[cont][2]=v[cont2].n2;
            cont++;

        }
    }
    cout<<sum<<endl<<n-1<<endl;
    for (int i=0 ; i<cont  ; i++)
        cout<<V[i][1]<<" "<<V[i][2]<<endl;


    return 0;
}