#include <bits/stdc++.h>

using namespace std;

const int Nmax = 200000 + 10;

int n , m , i , cost , node1 , node2 , sum;
int T[Nmax] , rang[Nmax];
vector < pair < int , pair < int , int > > > edge;
vector < pair < int , int > > ans;

int multime(int node)
{
    if (T[node] != node)
        T[node] = multime(T[node]);
    return T[node];
}

void uneste(int m1 , int m2)
{
    if (rang[m1] < rang[m2])
        T[m1] = m2;
    else
        T[m2] = m1;
    if (rang[m1] == rang[m2])
        rang[m1]++;
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

    scanf("%d %d", &n, &m);

    for (i = 1; i <= m; ++i)
    {
        scanf("%d %d %d", &node1 , &node2 , &cost);
        edge.push_back({cost,{node1,node2}});
    }

    sort(edge.begin() , edge.end());
    for (i = 1; i <= n; ++i) T[i] = i;

    for (i = 0; i < m; ++i)
    {
        cost = edge[i].first; tie(node1 , node2) = edge[i].second;
        int m1 = multime(node1);
        int m2 = multime(node2);

        if (m1 != m2)
        {
            uneste(m1 , m2);
            ans.push_back({node1 , node2});
            sum += cost;
        }
    }

    printf("%d\n%d\n", sum , ans.size());
    for (auto &it : ans)
        printf("%d %d\n", it.first , it.second);

    return 0;
}