// Kruskal with DSU
#include <bits/stdc++.h>
using namespace std;

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

class Edge
{
public:
    int x, y, c;

    Edge(int x, int y, int c): x(x), y(y), c(c){}

    bool operator<(Edge const& other) 
    {
        return c < other.c;
    }
};

int n, m, cost;
vector<Edge> edges, mst;
vector<int> parent, r;

void make_set(int x)
{
    parent[x] = x;
    r[x] = 0;
}

int find_set(int x)
{
    if(x == parent[x])
        return x;
    return parent[x] = find_set(parent[x]); //path compression
}

void union_sets(int a, int b)
{
    a = find_set(a);
    b = find_set(b);

    if(a != b)
    {
        if(r[a] < r[b])
            swap(a, b);
        parent[b] = a;
        if(r[a] == r[b])
            r[a]++;
    }

}

void read()
{
    fin>>n>>m;
    for(int i=0; i<m; i++)
    {
        int x, y, c;
        fin>>x>>y>>c;
        edges.push_back(Edge(x, y, c));
    }

    r.assign(n+1, 0);
    parent.assign(n+1, 0);
}

void solve()
{
    for(int i=1; i<=n; i++)
        make_set(i);

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

    for(auto &e:edges)
    {
        if(find_set(e.x) != find_set(e.y)) //in different trees
        {
            cost += e.c;
            mst.push_back(e);

            union_sets(e.x, e.y);
        }
    }
}

int main()
{
    read();
    solve();

    fout<<cost<<'\n'<<mst.size()<<'\n';
    for(auto &e:mst)
    {
        fout<<e.x<<' '<<e.y<<'\n';
    }

    return 0;
}