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

struct tip
{
    int x,y,z;

    bool operator<(const tip&other) const
    {
        return z<other.z;
    }
};

vector<tip> edges;
vector<pair<int,int> > sol;

const int maxN=(2e5)+5;

int t[maxN],n,m;

inline int getRoot(int x)
{
    int y=x;
    while(t[y]>0) y=t[y];

    int root=y;

    y=x;

    while(y!=root)
    {
        int aux=t[y];
        t[y]=root;
        y=aux;
    }

    return root;
}

inline void unite(int x,int y)
{
    if(t[x]<t[y])
    {
        t[x]+=t[y];
        t[y]=x;
    }
        else
    {
        t[y]+=t[x];
        t[x]=y;
    }
}

int x,y,z;
long long cost;

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)
        t[i]=-1;

    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        edges.push_back({x,y,z});
    }

    sort(edges.begin(),edges.end());

    for(auto it:edges)
    {
        int x=it.x;
        int y=it.y;
        int z=it.z;

        int rx=getRoot(x);
        int ry=getRoot(y);

        if(rx!=ry)
        {
            cost+=1LL*z;
            unite(rx,ry);
            sol.push_back(make_pair(x,y));
        }
    }

    printf("%lld\n",cost);

    printf("%d\n",n-1);

    for(auto it:sol)
        printf("%d %d\n",it.first,it.second);

    return 0;
}