#include <bits/stdc++.h>

using namespace std;

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

const int Nmax = 2e5 + 5;
vector<pair<int,pair<int,int>>> G;
vector<pair<int,int>> ans;
int uf[Nmax];
int cost;

int Find(int x)
{
    if(uf[x] < 0)
        return x;
    else
        return (uf[x] = Find(uf[x]));
}

void Union(int x, int y)
{
    x = Find(x);
    y = Find(y);
    if(x == y)
        return;
    if(uf[x] > uf[y])
        swap(x,y);

    uf[x] += uf[y];
    uf[y] = x;
}

int main()
{
    int N, M;
    in >> N >> M;
    for(int i = 1; i <= M; ++i)
    {
        int x, y, c;
        in >> x >> y >> c;
        G.push_back({c,{x,y}});
    }
    sort(G.begin(),G.end());
    for(int i = 1; i <= N; ++i)
        uf[i] = -1;
    for(int i = 0; i < M; ++i)
    {
        int nod1 = G[i].second.first;
        int nod2 = G[i].second.second;
        int T_nod1 = Find(nod1);
        int T_nod2 = Find(nod2);
        if(T_nod1 == T_nod2 && T_nod1 > 0)
            continue;
        Union(nod1,nod2);
        ans.push_back({nod1,nod2});
        cost += G[i].first;
    }
    out << cost << '\n';
    out << ans.size() << '\n';
    for(auto i : ans)
        out << i.first << " " << i.second << '\n';
    return 0;
}