#include<bits/stdc++.h>
#define NMAX 200004
#define cin fin
#define cout fout
using namespace std;
ifstream cin ("apm.in");
ofstream cout ("apm.out");
struct Muchie
{
    int x,y,cost;
    friend bool operator >(const Muchie &, const Muchie &);
};
bool operator >(const Muchie & m1, const Muchie & m2)
{
    return m1.cost > m2.cost;
}
priority_queue <Muchie, vector <Muchie>, greater <Muchie>>H;
vector <Muchie>sol;
int tata[NMAX],h[NMAX],n,costmin,m;
void citire();
void rezolvare();
int find(int x);
void Union(int x, int y);
void afisare();
int main()
{
    Muchie m;
    citire();
    while(sol.size()<n-1)
    {
        m=H.top();
        H.pop();
        int c1=find(m.x);
        int c2=find(m.y);
        if (c1!=c2)
        {
            costmin+=m.cost;
            sol.push_back(m);
            Union(c1,c2);
        }
    }
    afisare();
    return 0;
}
void citire()
{
    Muchie muc;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>muc.x>>muc.y>>muc.cost;
        H.push(muc);
    }
}
int find(int x)
{
    int r;
    r=x;
    while(tata[r])
        r=tata[r];
    while(tata[x])
    {
        int r2=tata[x];
        tata[x]=r;
        x=r2;
    }
    return r;
}
void Union(int x, int y)
{
    int i=find(x);
    int j=find(y);
    if (h[i]<h[j])
        tata[i]=j;
        else
        if(h[i]>h[j])
            tata[j] = i;
    else
    {
        tata[i]=j;
        h[j]++;
    }
}
void afisare()
{
    cout<<costmin<<'\n';
    cout<<sol.size()<<'\n';
    for (int i=0;i<sol.size();i++)
    {
        fout<<sol[i].x<<' '<<sol[i].y<<'\n';
    }
}