#include <bits/stdc++.h>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int t[200005],n,m,rang[200005],muchii,cost;
pair<int,pair<int,int>> v[400005];
vector <pair<int,int>> r;
int reprezentant(int x)
{
    if(x!=t[x])
        return reprezentant(t[x]);
    return t[x];
}
void uneste(int x,int y)
{
    x=reprezentant(x);
    y=reprezentant(y);
    if(rang[x]>rang[y])
    {
        t[y]=x;
        rang[x]+=rang[y];
        rang[y]=0;
    }
    else
    {
        t[x]=y;
        rang[y]+=rang[x];
        rang[x]=0;
    }
}
int main()
{
    f>>n>>m;
    for(int i=1; i<=m; i++)
    {
        f>>v[i].second.first>>v[i].second.second>>v[i].first;
    }
    sort(v+1,v+m+1);
    for(int i=1; i<=n; i++)
        t[i]=i;
    for(int i=1; i<=m; i++)
    {
        int x=v[i].second.first;
        int y=v[i].second.second;
        if(reprezentant(x)!=reprezentant(y))
        {
            uneste(x,y);
            muchii++;
            cost+=v[i].first;
            r.push_back({x,y});
        }
    }
    g<<cost<<'\n'<<muchii<<'\n';
    for(auto it : r)
    {
        g<<it.first<<' '<<it.second<<'\n';
    }
    return 0;
}