#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m;
vector<int> v[200005];
int p[200005],h[200005];
struct muchie
{
    int x,y,cost;
};
vector<muchie> mm;
bool crt(muchie a,muchie b)
{
    return a.cost<b.cost;
}
int find(int nod)
{
    int cop=nod,rez;
    while(nod!=p[nod])
        nod=p[nod];
    rez=nod;
    nod=cop;
    while(nod!=p[nod])
    {
        cop=p[nod];
        p[nod]=rez;
        nod=cop;
    }
    return rez;
}
void Union(int a,int b)
{
    if(a==b)
        return;
    if(h[a]<h[b])
        swap(a,b);
    else if(h[a]==h[b])
        h[a]++;
    p[b]=a;
}
int main()
{
    fin>>n>>m;
    int a,b,c;
    for(int i=1; i<=m; i++)
    {
        fin>>a>>b>>c;
        mm.push_back({a,b,c});
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i=1; i<=n; i++)
    {
        p[i]=i;
        h[i]=1;
    }
    sort(mm.begin(),mm.end(),crt);
    vector<pair<int,int>> r;
    int suma=0;
    for(int i=0; i<mm.size(); i++)
    {
        int fa=find(mm[i].x),fb=find(mm[i].y);
        if(fa!=fb)
        {
            Union(fa,fb);
            r.push_back({mm[i].x,mm[i].y});
            suma+=mm[i].cost;
        }
    }
    fout<<suma<<'\n'<<r.size()<<'\n';
    for(int i=0; i<r.size(); i++)
        fout<<r[i].first<<' '<<r[i].second<<'\n';
    return 0;
}