#include <bits/stdc++.h>
using namespace std;
#if true
ifstream fin ("apm.in");
ofstream fout ("apm.out");
#else
#define fin cin
#define fout cout
#endif

struct Edge
{
    int x,y;
    int cost;
};

bool edgeComp(Edge a, Edge b)
{
    return a.cost < b.cost;
}

int n,m;
int tata[200005];
Edge edges[400005];

int solCost, solCount;
vector<Edge> sol;

int Find(int node, int& height)
{
    int startNode = node;

    height = 0;
    int parent;
    while (node != 0)
    {
        parent = tata[node];
        if (parent == 0) break;
        node = parent;
        height++;
    }

    if (height > 0)
        tata[startNode] = node;

    return node;
}

int main()
{
    ios_base::sync_with_stdio(false);
    
    fin >> n >> m;   
    for (int i=1;i<=m;i++)
    {
        fin >> edges[i].x >> edges[i].y >> edges[i].cost;
    }

    sort(edges+1, edges + 1 + m, edgeComp);

    for (int i=1;i<=m;i++)
    {
        int heightX=0, heightY=0;
        int rootX = Find(edges[i].x,heightX);
        int rootY = Find(edges[i].y,heightY);

        if (rootX == rootY && rootX != 0)
            continue;

        sol.push_back(edges[i]);
        solCost+=edges[i].cost;
        solCount++;

        // union
        if (heightX<heightY)
            tata[rootX] = rootY;
        else
            tata[rootY] = rootX;


        if (solCount == n-1) 
            break;
    }


    fout << solCost<<'\n'<<solCount<<'\n';
    for (Edge e : sol) 
        fout<< e.y <<" "<< e.x<<'\n';
    return 0;
}