#include <bits/stdc++.h>

using namespace std;

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

typedef pair<int,pair<int,int>> piii;

const int nmax=1e6+5;

vector <piii> g, sol;
int n, m, t[nmax], h[nmax];

void init (int n)
{
    for (int i=1; i<=n; i++)
    {
        t[i]=i;
        h[i]=1;
    }
}

int getroot (int nod)
{
    if (t[nod]!=nod)
        t[nod]=getroot(t[nod]);
    return t[nod];
}

void unif (int x, int y)
{
    x=getroot(x);
    y=getroot(y);
    if (h[x]<h[y])
        t[x]=y;
    else if (h[x]>h[y])
        t[y]=x;
    else
    {
        t[y]=x;
        h[x]++;
    }
}

void solve ()
{
    int cost=0;
    sort(e.begin(),e.end());
    init(n);
    for (auto i:e)
    {
        int x=getroot(i.second.first);
        int y=getroot(i.second.second);
        if (x!=y)
        {
            unif(x,y);
            cost+=i.first;
            sol.push_back(i);
        }
    }
    fout << cost << '\n' << sol.size() << '\n';
    for (auto i:sol)
        fout << i.second.first << " " << i.second.second << '\n';
}

int main()
{
    fin >> n >> m;
    for (int i=1; i<=m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        g.push_back({c,{x,y}});
    }
    solve();
    return 0;
}