#include <bits/stdc++.h>

using namespace std;

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

const int INF = 999999999;
Edge v[400005];
bitset<400005> chosen;
int root[200005];
int s[200005];
int mini[200005];

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

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

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

void update(int a, int b)
{
    if(query(a,b)) return;
    if(s[getRoot(a)] > s[getRoot(b)]) swap(a,b);
    s[getRoot(b)] += s[getRoot(a)];
    s[getRoot(a)] = 0;
    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;
    v[m].c = INF;
    vector<Edge> ans;
    int cost = 0, cnt = n;
    build(n);
    while(cnt > 1)
    {
        for(int i=1; i<=n; ++i)
            mini[i] = m;
        for(int i=0; i<m; ++i)
            if(!chosen[i] && !query(v[i].a, v[i].b))
            {
                if(v[mini[getRoot(v[i].a)]].c > v[i].c)
                    mini[getRoot(v[i].a)] = i;
                if(v[mini[getRoot(v[i].b)]].c > v[i].c)
                    mini[getRoot(v[i].b)] = i;
            }
        for(int i=1; i<=n; ++i)
        {
            if(root[i] == i)
            {
                if(!chosen[mini[i]])
                {
                    cost += v[mini[i]].c;
                    ans.push_back(v[mini[i]]);
                    update(v[mini[i]].a, v[mini[i]].b);
                    --cnt;
                    chosen[mini[i]] = 1;
                }
            }
        }
    }
    fout<<cost<<'\n'<<n-1<<'\n';
    for(Edge &i : ans)
        fout<<i.a<<' '<<i.b<<'\n';
    return 0;
}