#include <cstdio>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

class MultimiDisjuncte{
private:
    int x[200005];

    int gasireParinte(int a)
    {
        while(x[a] != a)
        {
            a = x[a];
        }

        return a;
    }

public:
    MultimiDisjuncte()
    {
        for(int i = 1; i < 200005; i++)
        {
            x[i] = i;
        }
    }

    bool suntUnite(int nr1, int nr2)
    {
        if(gasireParinte(nr1) == gasireParinte(nr2))
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    void unire(int nr1, int nr2)
    {
        x[gasireParinte(nr1)] = gasireParinte(nr2);
    }

}multime;

int n, m;
int sum = 0;
int nr = 0;

vector<pair<int, int> > vecini[200005];
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int> >, greater<tuple<int, int, int> > > Q;
vector<pair<int, int> > sol;

void citire()
{
    scanf("%d %d", &n, &m);

    int tmp1, tmp2, tmp3;

    for(int i = 1; i <= m; i++)
    {
        scanf("%d %d %d", &tmp1, &tmp2, &tmp3);

        vecini[tmp1].push_back(make_pair(tmp3, tmp2));
        vecini[tmp2].push_back(make_pair(tmp3, tmp1));

        Q.push(make_tuple(tmp3, tmp1, tmp2));
    }
}

void solve()
{
    while(!Q.empty())
    {
        int tmp1, tmp2, tmp3;

        tmp3 = get<0>(Q.top());
        tmp1 = get<1>(Q.top());
        tmp2 = get<2>(Q.top());

        if(multime.suntUnite(tmp1, tmp2) == false)
        {
            multime.unire(tmp1, tmp2);
            sum += tmp3;
            nr++;

            sol.push_back(make_pair(tmp1, tmp2));
        }

        Q.pop();
    }

    printf("%d\n%d\n", sum, nr);

    for(int i = 0; i < nr; i++)
    {
        printf("%d %d\n", sol[i].second, sol[i].first);
    }
}

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

    citire();
    solve();

    return 0;
}