#include <bits/stdc++.h>

using namespace std;

struct Edge
{
    int a,b,c;
};

Edge v[400000];
int root[200005];
int s[200005];

void build(int n)
{
    for(int i=1; i<=n; ++i)
    {
        root[i] = i;
        s[i] = 1;
    }
}

int getRoot(int node)
{
    int x = node;
    while(root[x] != x)
        x = root[x];
    while(root[node] != node)
    {
        node = root[node];
        root[node] = x;
    }
    return node;
}

bool query(int a, int b)
{
    return getRoot(a) == getRoot(b);
}

void update(int a, int b)
{
    if(query(a,b)) return;
    root[getRoot(a)] = getRoot(b);
}

signed main()
{
    ifstream fin ("apm.in");
    ofstream fout ("apm.out");
    ios::sync_with_stdio(false); fin.tie(0); fout.tie(0);
    int n,m; fin>>n>>m;
    for(int i=0; i<m; ++i)
        fin>>v[i].a>>v[i].b>>v[i].c;
    sort(v, v+m, [](const Edge &x, const Edge &y){return x.c < y.c;});
    build(n);
    vector<Edge> ans;
    int cost = 0;
    for(int i=0; i<m; ++i)
        if(!query(v[i].a, v[i].b))
        {
            cost += v[i].c;
            ans.push_back(v[i]);
            update(v[i].a, v[i].b);
        }
    fout<<cost<<'\n'<<n-1<<'\n';
    for(Edge &i : ans)
        fout<<i.a<<' '<<i.b<<'\n';
    return 0;
}