# include <fstream>
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# define nmax 200005
using namespace std;
ifstream fi("apm.in");
ofstream fo("apm.out");
int s[nmax];
struct cc{int x;int y;int z;};
cc S[nmax*2];
int x[nmax],y[nmax];
int find(int a)
{
    return (a==s[a]) ? a : (s[a]=find(s[a]));
}
bool compare(cc a,cc b) {return (a.z<b.z);}
int main(void)
{
    int n,m;
    fi>>n>>m;
    for (int i=1;i<=m;++i)
    {
        int X,Y,Z;
        fi>>X>>Y>>Z;
        S[i].x=X;S[i].y=Y;S[i].z=Z;
    }
    for (int i=1;i<=n;++i) s[i]=i;
    sort(S+1,S+1+m,compare);
    int c,d,C=0,p=0;
    for (int i=1;i<=m;++i)
    {
        c=find(S[i].x);d=find(S[i].y);
        if (c!=d)
        {
            C+=S[i].z;
            ++p;x[p]=S[i].x;y[p]=S[i].y;
            s[c]=d;
        }
    }
    fo<<C<<"\n"<<n-1<<"\n";
    for (int i=1;i<=p;++i) fo<<y[i]<<" "<<x[i]<<"\n";
}