#include <bits/stdc++.h>

using namespace std;

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

vector <pair<int,pair<int,int>>> e, sol;
int n, m, t[100005], rang[100005];

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

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

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

void reuneste (int i, int j)
{
    i=multime(i);
    j=multime(j);
    if (i==j)
        return;
    if (rang[i]<rang[j])
        t[i]=j;
    else
        t[j]=i;
    if (rang[i]==rang[j])
        rang[i]++;
}

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

int main()
{
    read();
    solve();
    return 0;
}