#include <bits/stdc++.h>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie
{
    int x,y,cost;
    bool operator <(const muchie &A)const
    {
        return cost<A.cost;
    }
};
int n,m;
muchie L[200005];
int t[200005], a[200005], b[200005];

inline void Union(int x, int y)
{
    t[y]=x;
}

inline int Find(int x)
{
    int rad, y;
    rad=x;
    while(t[rad])
        rad=t[rad];
    while(t[x])
    {
        y=t[x];
        t[x]=rad;
        x=y;
    }
    return rad;
}

inline void Citire()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        fin>>L[i].x>>L[i].y>>L[i].cost;
    }
    sort(L+1, L+m+1);
}

inline void Rezolvare()
{
    int s=0,top=0;
    for(int i=1; i<=m; i++)
    {
        int x=Find(L[i].x), y=Find(L[i].y);
        if(x!=y)
        {
            Union(x,y);
            s+=L[i].cost;
            a[++top]=L[i].x;
            b[top]=L[i].y;
        }
    }
    fout<<s<<"\n"<<top<<"\n";
    for(int i=1; i<=top; i++)
    {
        fout<<a[i]<<" "<<b[i]<<"\n";
    }
}

int main()
{
    Citire();
    Rezolvare();
    return 0;
}