#include <bits/stdc++.h>

using namespace std;

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

vector<pair<int,pair<int,int>>> edges;
vector<pair<int,int>> res;

int parent[200005], dim[200005];
int n,m,x,y,w;


//radacina arborelui in care se afla x
int find_root(int node)
{
    while(node != parent[node])
        node=parent[node];

    return node;
}


void union_k(int x,int y)
{
    int root_x=find_root(x);
    int root_y=find_root(y);

    if(dim[root_x]>=dim[root_y])
    {
        parent[root_y]=root_x;
        dim[root_x]+=dim[root_y];
    }
    else
    {
        parent[root_x] = root_y;
        dim[root_y] += dim[root_x];
    }
}

int kruskall()
{
    int min_weight = 0;
    sort(edges.begin(), edges.end());

    for(auto edge : edges)
    {
        if(find_root(edge.second.first) != find_root(edge.second.second)) //nodurile nu sunt in ac comp conexa
        {
            min_weight += edge.first;
            union_k(edge.second.first, edge.second.second);
            res.push_back({edge.second.second, edge.second.first});
            //cout<<edge.first<<" ";

        }
        //cout<<edge.first<<" ";
    }
    return min_weight;
}

int main()
{

    in>>n>>m;

    for(int i=1; i<=n; ++i)
    {
        dim[i]=1;
        parent[i]=i;
    }
    for(int i=1; i<=m; i++)
    {
        in>>x>>y>>w;
        edges.push_back({w,{x,y}});
    }
    out<<kruskall()<<"\n";

    out<<res.size()<<"\n";
    for(int i=0; i<res.size(); i++)
       out<<res[i].first<<" "<<res[i].second<<"\n";

    return 0;

}