#include <bits/stdc++.h>
#define NMAX 200001
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct Muchie
{
    int x,y;
    int 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 n,nr,t[NMAX],l[NMAX];
int costmin;

int fnd(int x)
{
    int r,y;
    r=x;
    while(t[r]!=r)
        r=t[r];
    y=x;
    int tata;
    while(y!=r)
    {
        tata=t[y];
        t[y]=r;
        y=tata;
    }
    return r;
}
void unire(int x, int y)
{
    if (l[x]>l[y])
        t[y]=fnd(x);
    else
        t[x]=fnd(y);
    if (l[x]==l[y])
        l[y]++;
}
int main()
{
    fin>>n>>nr;
    for(int i=1;i<=n;i++)
        t[i]=i;
    Muchie m;
    for(int i=1;i<=nr;i++)
    {
        fin>>m.x>>m.y>>m.cost;
        H.push(m);
    }
    while(sol.size()<n-1)
    {
        m=H.top();
        H.pop();
        int c1=fnd(m.x);
        int c2=fnd(m.y);
        if(c1!=c2)
        {
            costmin+=m.cost;
            sol.push_back(m);
            unire(c1,c2);
        }
    }
    fout<<costmin<<'\n'<<sol.size()<<'\n';
    for(int i=0;i<sol.size();i++)
        fout<<sol[i].x<<" "<<sol[i].y<<'\n';
    return 0;
}