#include <bits/stdc++.h>

using namespace std;
struct cez
{
    int f,s,c;
}v[400005],ans[400005];
bool cmp(cez a, cez b)
{
    return a.c<b.c;
}
int father[200005],height[200005];
int rad(int node)
{
    int root=node;
    while(root!=father[root])
        root=father[root];
    while(node!=root)
    {
        int tmp=father[node];
        father[node]=root;
        node=tmp;
    }
    return root;
}
void unite(int x, int y)
{
    int rootx=rad(x),rooty=rad(y);
    if(height[rootx]>height[rooty])
        father[rooty]=rootx;
    else if(height[rootx]<height[rooty])
        father[rootx]=rooty;
        else
        {
            father[rooty]=rootx;
            height[rootx]++;
        }
}
int main()
{
    ifstream cin("apm.in");
     ofstream cout("apm.out");
    int n,m,x,y,c,comp=0,cost=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        father[i]=i;
        height[i]=1;
    }
    for(int i=0;i<m;i++)
     cin>>v[i].f>>v[i].s>>v[i].c;
     sort(v,v+m,cmp);
     for(int i=0;i<m;i++)
     {
         int rootx=rad(v[i].f),rooty=rad(v[i].s);
         if(rootx!=rooty)
         {
             comp++;
             cost+=v[i].c;
             ans[comp].f=v[i].f;
             ans[comp].s=v[i].s;
             unite(v[i].f, v[i].s);
         }

     }
     cout<<cost<<'\n';
     cout<<comp<<'\n';
     for(int i=1;i<=comp;i++)
     {
         cout<<ans[i].s<<" "<<ans[i].f<<'\n';
     }
    return 0;
}