#include <bits/stdc++.h>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct edge{
    int a;
    int b;
    int cost;
    bool operator < (const edge &other) const{
        return cost < other.cost;
    }
};

int n, m;
const int nmax=2e5, mmax=4e5, cmax=1000;
vector<edge> muchii;
int parinte[nmax+1], rang[nmax+1];
int costMin, arblen;
vector<edge> arbMin;

int root(int x)
{
    if(x!=parinte[x])
        parinte[x]=root(parinte[x]);
    return parinte[x];
}

bool joined(int a, int b){
    return root(a)==root(b);
}

void join(edge muchie)
{
    int a=root(muchie.a), b=root(muchie.b);
    if(rang[a]<rang[b])
    {
        parinte[a]=root(b);
        rang[a]=rang[b]=max(rang[a]+1, rang[b]);
    }
    else
    {
        parinte[b]=root(a);
        rang[a]=rang[b]=max(rang[b]+1, rang[a]);
    }
    costMin+=muchie.cost;
    arblen++;
    arbMin.push_back(muchie);
}

int main()
{
    fin >> n >> m;
    int a, b, c;
    for(int i=1; i<=m; i++)
    {
        fin >> a >> b >> c;
        muchii.push_back({a,b,c});
    }
    sort(muchii.begin(), muchii.end());

    for(int i=1; i<=n; i++)
        parinte[i]=i;
    costMin=0;
    arblen=0;
    for(int i=0; i<m; i++)
        if(!joined(muchii[i].a, muchii[i].b))
            join(muchii[i]);
    fout << costMin << '\n' << arblen << '\n';
    for(edge x: arbMin)
        fout << x.a << ' ' << x.b << '\n';
    return 0;
}