#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

vector <int> parent, set_rank;

void make_set(int v)
{
    parent[v]=v;
    set_rank[v]=0;
}

int find_set(int v)
{
    while(v!=parent[v])
        v=parent[v];
    return v;
}

void union_sets(int a,int b)
{
    a=find_set(a);
    b=find_set(b);
    if(a!=b)
    {
        if(set_rank[a]<set_rank[b])
            swap(a,b);
        parent[b]=a;
        if(set_rank[a]==set_rank[b])
            set_rank[a]++;
    }
}

struct Edge
{
    int u,v,weight;
    bool operator<(Edge const &other)
    {
        return weight<other.weight;
    }
};

vector <Edge> edges,result;
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

    int n,m,i,cost=0,x,y,c;
    Edge temp;
    scanf("%d%d",&n,&m);
    parent.resize(n+1);
    set_rank.resize(n+1);
    for(i=0;i<n;i++)
        make_set(i);

    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        temp.u=x;
        temp.v=y;
        temp.weight=c;
        edges.push_back(temp);
    }

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

    for(Edge e: edges)
    {
        if(find_set(e.u)!=find_set(e.v))
        {
            cost+=e.weight;
            result.push_back(e);
            union_sets(e.u,e.v);
        }
    }

    printf("%d\n%d\n",cost,result.size());
    for(Edge e: result)
        printf("%d %d\n",e.u,e.v);

    fclose(stdin);
    fclose(stdout);
    return 0;
}