#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int n,m;

struct muchie
{
    int a,b,cost;
    muchie(int x,int y,int z)
    {
        a=x;
        b=y;
        cost=z;
    }
};

struct comparare
{
    inline bool operator()(muchie a,muchie b)
    {
        return a.cost<b.cost;
    }
};

vector<muchie>graf;
int parent[200001],rang[200001];

int get_parent(int x)
{
    int pr;
    for(pr=x; parent[pr]!=pr; pr=parent[pr]);

    while(parent[x] != x)
    {
        int y = parent[x];
        parent[x] = pr;
        x = y;
    }

    return pr;
}


void join(int x,int y)
{
    int parent_x=get_parent(x);
    int parent_y=get_parent(y);
    if (rang[parent_x] > rang[parent_y])
        parent[parent_x]=parent_y;
    else parent[parent_y]=parent_x;
}

int find(int x,int y)
{
    int parent_x=get_parent(x);
    int parent_y=get_parent(y);
    return parent_x==parent_y;
}

void citire()
{
    scanf("%d %d ",&n,&m);
    while(m--)
    {
        int x,y,z;
        scanf("%d %d %d ",&x,&y,&z);
        muchie m1(x,y,z);
        graf.push_back(m1);
        muchie m2(y,x,z);
        graf.push_back(m2);
    }
}

vector<pair<int,int> >apm;
int suma_costuri;


void rezolvare()
{
    for(int i=1; i<=n; i++)
        parent[i]=i;

    sort(graf.begin(),graf.end(),comparare());
    m=graf.size();
    for(int i=0;i<m;i++)
    {
        if(get_parent(graf[i].a)!=get_parent(graf[i].b))
        {
            apm.push_back(make_pair(graf[i].a,graf[i].b));
            suma_costuri+=graf[i].cost;
            join(graf[i].a,graf[i].b);
        }
    }
}

void afisare()
{
    int m=apm.size();
    printf("%d\n%d\n",suma_costuri,m);
    for(int i=0;i<m;i++)
    {
        printf("%d %d\n",apm[i].first,apm[i].second);
    }
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire();
    rezolvare();
    afisare();
    return 0;
}