#include <bits/stdc++.h>

using namespace std;

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

int n, m, solw;
int p[102], rnk[102];
struct edge { int c,x,y;} ed[9002];
vector < pair<int,int> > sol;

int find_set(int x)
{
    if(p[x] == x) return x;
    return find_set(p[x]);
}

void union_set(int left, int right)
{
    left = find_set(left);
    right = find_set(right);

    if(rnk[left] > rnk[right]) p[right] = left;
    else p[left] = right;

    if(rnk[left] == rnk[right]) ++rnk[right];
}

bool cmp(edge a,edge b)
{
    if(a.c > b.c) return 0;
    else if(a.c == b.c && a.x > b.x) return 0;
    else if(a.c == b.c && a.x == b.x && a.y > b.y) return 0;
    return 1;
}

void Kruskal()
{
    for(int i = 1; i <= n; ++i)
        p[i] = i;

    sort(ed + 1, ed + 1 + m,cmp);

    for(int i = 1; i <= m; ++i)
    {
        int us = find_set(ed[i].x);
        int ud = find_set(ed[i].y);

        if( us != ud)
        {
            solw += ed[i].c;
            sol.push_back({ed[i].x,ed[i].y});
            union_set(us,ud);
        }
    }

}

int main()
{
    f >> n >> m ;
    for (int i = 1; i <= m; ++i)
    {
        f >> ed[i].x >> ed[i].y >> ed[i].c;

    }

    Kruskal();

    g << solw << "\n";

    for(auto x : sol)
     g << x.first << " " << x.second << "\n";

    return 0;
}