#include <bits/stdc++.h>

using namespace std;
int stramos[200005], sz[200005];
int find_parent(int a)
{
    if(stramos[a]==a)
        return a;
    return stramos[a]=find_parent(stramos[a]);
}
void unite(int a, int b)
{
    a=find_parent(a);
    b=find_parent(b);
    if(sz[a]>sz[b])
        swap(a,b);
    stramos[a]=b;
    sz[b]+=sz[a];
}
int main()
{
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        stramos[i]=i, sz[i]=1;
    vector<tuple<int,int,int>>edge(m);
    for(auto &[cost, a, b]: edge)
    {
        cin>>a>>b>>cost;
    }
    sort(edge.begin(), edge.end());
    vector<pair<int,int>>muchii_pastrate;
    int rasp=0;
    for(auto [cost, a, b]: edge)
    {
        if(find_parent(a)==find_parent(b))
            continue;
        muchii_pastrate.push_back({a,b});
        rasp+=cost;
        unite(a,b);
    }
    cout<<rasp<<'\n'<<n-1<<'\n';
    for(auto x: muchii_pastrate)
        cout<<x.first<<" "<<x.second<<'\n';
    return 0;
}