//kruskal
#include <bits/stdc++.h>
#define pii pair<int,int>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct muchie{
    int x,y,cost;
}muchii[400200];

bool cand(muchie a, muchie b){
    return a.cost<b.cost;
}

int n,m,s,maxim,tata[100200],rang[100200];
vector <pii> rez;

int radacina(int x)
{
    if(x==tata[x])
        return x;
    return tata[x]=radacina(tata[x]);
}

void uneste(int a, int b)
{
    int ra=radacina(a), rb=radacina(b);
    if(ra==rb)
        return ;
    if(rang[ra]>rang[rb])
        tata[rb]=ra;
    else
    {
        tata[ra]=rb;
        if(rang[ra]==rang[rb])
            rang[rb]++;
    }
}

int main()
{
    f>>n>>m;
    for(int i=1; i<=m; i++)
        f>>muchii[i].x>>muchii[i].y>>muchii[i].cost;
    sort(muchii+1, muchii+m+1, cand);

    for(int i=1; i<=n; i++)
        tata[i]=i, rang[i]=1;
    for(int i=1; i<=m; i++)
    {
        int x=muchii[i].x, y=muchii[i].y;
        if(radacina(x)!=radacina(y))
        {
            uneste(x,y);
            s += muchii[i].cost;
            rez.push_back({muchii[i].x,muchii[i].y});
        }
    }
    g<<s<<'\n'<<n-1<<'\n';
    for(auto it:rez)
        g<<it.first<<' '<<it.second<<'\n';
    return 0;
}