#include <bits/stdc++.h>

using namespace std;
struct muchii
{
    int x,y,cost;
};
vector<muchii>graph;
int parent[200005], sz[200005];
bool cmp(muchii a, muchii b)
{
    return a.cost<=b.cost;
}
int find_parent(int x)
{
    if(parent[x]==x)
        return x;
    parent[x]=find_parent(parent[x]);
}
void unite(int x, int y)
{
    x=find_parent(x);
    y=find_parent(y);
    if(sz[x]<sz[y])
        swap(x,y);
    parent[y]=x;
    sz[x]+=sz[y];
}
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++)
        parent[i]=i, sz[i]=1;
    for(int i=1; i<=m; i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        graph.push_back({a,b,c});
    }
    sort(graph.begin(), graph.end(), cmp);
    int rasp=0;
    vector<muchii>arbore;
    for(auto muchie: graph)
    {
        if(find_parent(muchie.x)==find_parent(muchie.y))
            continue;
        rasp+=muchie.cost;
        unite(muchie.x, muchie.y);
        arbore.push_back(muchie);
    }
    cout<<rasp<<'\n'<<n-1<<'\n';
    for(auto x: arbore)
        cout<<x.x<<" "<<x.y<<'\n';
    return 0;
}