#include <cstdio>
#include <vector>
#include <algorithm>
#define NMAX 200010
using namespace std;
int n,m,x,y,c,i,T[NMAX],rang[NMAX],cost,x2,y2,S;
vector < pair < int , pair < int , int > > > G;
vector < pair < int, int > > sol;

int multime(int node1)
{
    int node2;
    if(T[node1]==node1)
        return node1;
    node2=multime(T[node1]);
    T[node1]=node2;
    return node2;
}

void reuniune(int node1,int node2)
{
    if(rang[node1]>rang[node2])
        T[node2]=node1;
    else T[node1]=node2;
    if(rang[node1]==rang[node2])
        ++rang[node2];
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1; i<=m; ++i)
    {
        scanf("%d%d%d",&x,&y,&c);
        G.push_back(make_pair(c,make_pair(x,y)));
    }
    for(i=1; i<=n; ++i)
        T[i]=i;
    sort(G.begin(),G.end());
    for(i=0; i<m; ++i)
    {
        x2=G[i].second.first;
        y2=G[i].second.second;
        x=multime(x2);
        y=multime(y2);
        if(x!=y)
        {
            cost+=G[i].first;
            sol.push_back(make_pair(x2,y2));
            reuniune(x,y);
        }
    }
    S=sol.size();
    printf("%d\n%d\n",cost,S);
    for(i=0; i<S; ++i)
        printf("%d %d\n",sol[i].first,sol[i].second);
    return 0;
}