#include <cstdio>
#include <vector>
#include <algorithm>
#define N 200002
#define M 400002

using namespace std;

int n,m,cost,p[N];

struct muchie{
    int x,y,c;
};

vector<muchie>G;
vector<muchie>A;
vector<int>P[N];

bool MinCost(const muchie a, const muchie b)
{
    return a.c<b.c;
}

void read()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        muchie g;
        scanf("%d%d%d", &g.x, &g.y, &g.c);
        G.push_back(g);
    }
    for(int i=1; i<=n; i++)
    {
        p[i]=i;
        P[i].push_back(i);
    }
    sort(G.begin(),G.end(),MinCost);
}

void solve()
{
    int min1, max1;
    for(int i=0; A.size()<n-1; i++)
    {
        if(p[G[i].x]!=p[G[i].y])
        {
            A.push_back(G[i]);
            cost=cost+G[i].c;
            if(P[p[G[i].x]].size()<P[p[G[i].y]].size())
            {
                min1=p[G[i].x];
                max1=p[G[i].y];
            }
            else
            {
                min1=p[G[i].y];
                max1=p[G[i].x];
            }
            while(P[min1].size())
            {
                P[max1].push_back(P[min1][0]);
                p[P[min1][0]]=max1;
                P[min1].erase(P[min1].begin());
            }
        }
    }
    printf("%d\n%d\n", cost, A.size());
    for(int i=0; i<A.size(); i++)
    {
        printf("%d %d\n", A[i].x, A[i].y);
    }
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    read();
    solve();
    return 0;
}