#include<stdio.h>
#include<vector>
#include<set>
using namespace std;

#define FIN "apm.in"
#define FOUT "apm.out"
#define MAXSIZE 200002

set< pair< int,pair<int,int> > > s;
int father[MAXSIZE];
vector<pair<int,int> > tree;
int ranc[MAXSIZE];

int n,m,nr;
int minValue;

int find(int x)
{
    if(father[x] == x)
        return x;
    else return find(father[x]);
}

void uniune(int a, int b)
{
    int aRoot = find(a);
    int bRoot = find(b);
    if(aRoot == bRoot)
        return;
    if(ranc[aRoot]<ranc[bRoot])
    {
        father[aRoot] = bRoot;
    }
    else if(ranc[aRoot]>ranc[bRoot])
        father[bRoot] = aRoot;
    else
        father[bRoot] = aRoot;
        ranc[aRoot]++;

}
int read()
{
    scanf("%d %d",&n,&m);
    int x,y,z;
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&x,&y,&z);
        s.insert(make_pair(z, make_pair(x,y)));
    }

}


int main()
{
    freopen(FIN,"r",stdin);
    freopen(FOUT,"w",stdout);
    read();

    //init
    for(int i=1;i<=n;i++)
    {
        father[i] = i;
    }
    //end of init
    int cost,x,y;
    while(nr<n-1)
    {
        cost = (*s.begin()).first;
        x = (*s.begin()).second.first;
        y = (*s.begin()).second.second;
        if(find(x) != find(y))
        {
            uniune(x,y);
            minValue += cost;
            nr++;
            tree.push_back(make_pair(x,y));
        }

        s.erase(s.begin());

    }

    //Write
    printf("%d\n%d\n",minValue,nr);
    for(int i=0;i<nr;i++)
    {
        x = tree[i].first;
        y = tree[i].second;

        printf("%d %d\n",x,y);
    }

    return 0;
}