#include <bits/stdc++.h>
using namespace std;

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

const int maxn = 2e5+2;
int n, m, f[maxn];
struct str{
    int x, y, c;
};
vector<str>G;

inline bool cmp(const str &a, const str &b)
{
    return a.c<b.c;
}

int find_f(int nod)
{
    if(nod!=f[nod])
    {
        return f[nod]=find_f(f[nod]);
    }
    return nod;
}

void APM()
{
    int muchii=0, cost=0;
    vector<pair<int, int> >A;
    sort(G.begin(),G.end(),cmp);
    for(int i=1; i<=n; i++)
    {
        f[i]=i;
    }
    for(int i=0; muchii<n-1; i++)
    {
        if(find_f(f[G[i].x])!=find_f(f[G[i].y]))
        {
            muchii++;
            cost=cost+G[i].c;
            f[find_f(G[i].y)]=find_f(f[G[i].x]);
            A.push_back({G[i].x,G[i].y});
        }
    }
    fout<<cost<<'\n'<<n-1<<'\n';
    for(auto it:A)
    {
        fout<<it.first<<' '<<it.second<<'\n';
    }
}

int main()
{
    int x, y, c;
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        fin>>x>>y>>c;
        G.push_back({x,y,c});
    }
    APM();

    return 0;
}