#include <bits/stdc++.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
#define cout g
vector<int>papa;
vector<int>rnk;
struct edge
{
    int x,y,c;
};
bool comp(edge a, edge b)
{
    return a.c < b.c;
}
int find1(int a)
{
    if(a!=papa[a])
    {
        papa[a]=find1(papa[a]);
    }else
    {
        return papa[a];
    }
}
void unite(int a, int b)
{
    int rootX = find1(a);
    int rootY = find1(b);
    if(rootX!=rootY)
    {
        if(rnk[rootX]>rnk[rootY])
        {
            papa[rootY]=rootX;
        }else if(rnk[rootX]<rnk[rootY])
        {
            papa[rootX]=rootY;
        }else
        {
            papa[rootY]=rootX;
            rnk[rootX]++;
        }
    }
}
int main()
{
    int n, m;
    f >> n >> m;
    vector<edge> v(m+1);
    for(int i=1; i<=m; i++)
    {
        f >> v[i].x >> v[i].y >> v[i].c;
    }
    rnk.resize(n+1,1);
    papa.resize(n+1);
    //fiecare nod e tatal lui
    for(int i=1; i<=n; i++)
        papa[i]=i;

    sort(v.begin()+1, v.end(), comp);
    vector<edge> ap;
    int tw = 0;
    for(edge i : v)
    {
        if(find1(i.x)!=find1(i.y))
        {
            unite(i.x, i.y);
            ap.push_back(i);
            tw+=i.c;
        }
    }

    cout << tw << '\n';
    cout << ap.size() << '\n';
    for(auto i:ap)
    {
        cout << i.y << " " <<  i.x  << '\n';
    }
}