#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

const int NMAX=2e5+5, MMAX=4e5+5;
int n, m, cst;
struct edge
{
    int u, v, c;
    friend bool operator<(const edge a, const edge b)
    {
        return a.c<b.c;
    }
}e[MMAX];
vector<edge> sol;

struct DSU
{
    int p[NMAX], sz[NMAX];
    void init()
    {
        for(int i=1;i<=n;i++)
            p[i]=i, sz[i]=1;
    }
    int find(int u)
    {
        return (u==p[u])?u:u=find(p[u]);
    }
    void merge(int a, int b)
    {
        a=find(a); b=find(b);
        if(a==b)
            return;
        if(sz[a]<sz[b])
            swap(a, b);
        p[b]=a;
        sz[a]+=sz[b];
    }
}ds;

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>e[i].u>>e[i].v>>e[i].c;
    sort(e+1, e+m+1);
    ds.init();
    for(int i=1;i<=m;i++)
        if(ds.find(e[i].u)!=ds.find(e[i].v))
        {
            ds.merge(e[i].u, e[i].v);
            sol.push_back(e[i]);
            cst+=e[i].c;
        }
    cout<<cst<<'\n'<<sol.size()<<'\n';
    for(auto x:sol)
        cout<<x.u<<" "<<x.v<<'\n';
    return 0;
}