#include <bits/stdc++.h>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
const int N=2e5+10;
struct muc{
    int x,y,c;
};
int tata[N],n,suma,nrc[N];
vector <muc> muchie;
bool comp(muc a,muc b)
{
    return a.c<b.c;
}
int rad(int x)
{
    if(tata[x]==0)
    {
        return x;
    }
    tata[x]=rad(tata[x]);
    return tata[x];
}
void actual(int x,int y)
{
    tata[y]=rad(x);
}
void adauga(int x,int y)
{
    x=rad(x);
    y=rad(y);
    if(nrc[x]<nrc[y])
    {
        actual(x,y);
        nrc[y]+=nrc[x];
    }
    else
    {
        actual(y,x);
        nrc[x]+=nrc[y];
    }
}
int main()
{
    int m;
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        f>>x>>y>>z;
        muc aux;
        aux.x=x;
        aux.y=y;
        aux.c=z;
        muchie.push_back(aux);
    }
    for(int i=1;i<=n;i++)
    {
        tata[i]=0;
        nrc[i]=1;
    }
    sort(muchie.begin(),muchie.end(),comp);
    vector <pair<int,int>> afis;
    for(auto i:muchie)
    {
        if(rad(i.x)!=rad(i.y))
        {
            adauga(i.x,i.y);
            suma+=i.c;
            afis.push_back({i.x,i.y});
        }
    }
    g<<suma<<"\n"<<afis.size()<<"\n";
    for(auto i:afis)
    {
        g<<i.second<<" "<<i.first<<"\n";
    }
    return 0;
}