#include <bits/stdc++.h>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int get_root(int node, vector<int> &node_father)
{
    if(node==node_father[node])
        return node;
    else
    {
        node_father[node]=get_root(node_father[node],node_father);
        return node_father[node];
    }
}

int main()
{
    int n,m,x,y,cost,total_cost=0;
    fin>>n>>m;
    vector<tuple<int,int,int>> edges;
    vector<tuple<int,int>> part_edges;
    vector<int> node_father(n+5);
    for(int i=1;i<=n;i++)
        node_father[i]=i;
    for(;m;m--)
    {
        fin>>x>>y>>cost;
        edges.push_back(make_tuple(cost,x,y));
    }
    sort(edges.begin(),edges.end());
    int root_x,root_y;
    for(int i=0;i<edges.size()&&part_edges.size()<n;i++)
    {
        tie(cost,x,y)=edges[i];
        root_x=get_root(x,node_father);
        root_y=get_root(y,node_father);
        if(root_x!=root_y)
        {
            node_father[root_x]=root_y;
            part_edges.push_back(make_tuple(x,y));
            total_cost+=cost;
        }
    }
    fout<<total_cost<<'\n'<<part_edges.size()<<'\n';
    for(int i=0;i<part_edges.size();i++)
    {
        tie(x,y)=part_edges[i];
        fout<<y<<' '<<x<<'\n';
    }
    return 0;
}