#include <bits/stdc++.h>

using namespace std;

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

struct comp
{
    bool operator()(const Edge &x, const Edge &y) const
    {
        return x.c > y.c;
    }
};

vector<Edge> v[200005];
priority_queue<Edge, vector<Edge>, comp> pq;
bitset<200005> chosen;
int cnt;

void push(int node)
{
    ++cnt;
    chosen[node] = 1;
    for(Edge &i : v[node])
        if(!chosen[i.b])
            pq.push(i);
}

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)
    {
        int a,b,c;
        fin>>a>>b>>c;
        v[a].push_back({a,b,c});
        v[b].push_back({b,a,c});
    }
    vector<Edge> ans;
    int cost = 0;
    push(1);
    while(cnt < n)
    {
        Edge e = pq.top(); pq.pop();
        if(chosen[e.b]) continue;
        ans.push_back(e);
        cost += e.c;
        push(e.b);
    }
    fout<<cost<<'\n'<<n-1<<'\n';
    for(Edge &i : ans)
        fout<<i.a<<' '<<i.b<<'\n';
    return 0;
}