#include <bits/stdc++.h>
#define Nmax 200002

using namespace std;

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

int poz[2*Nmax] , l[Nmax] ,i,m,n,xx,yy;

struct{
    int x, y,c;
}v[2*Nmax];

inline void read()
{
    f >> n >> m;
    for(i = 1;i <= m;i++)
        f >> v[i].x >> v[i].y >> v[i].c , poz[i] = i;

    for(i = 1;i <= n;i++)
        l[i] = i;
}

bool cmp(int a,int b)
{
    return v[a].c < v[b].c;
}

int grupa(int x)
{
    if(l[x] == x)
        return x;
    l[x] = grupa(l[x]);
    return l[x];
}

void uneste(int x,int y)
{
    l[grupa(x)] = grupa(y);
}

inline void kruskal()
{
    queue < int > Q; int ct = 0;
    for(i = 1;i <= m;i++)
    {
        xx = v[poz[i]].x; yy = v[poz[i]].y;
        if(grupa(xx) != grupa(yy))
        {
            ct += v[poz[i]].c;
            Q.push(poz[i]);
            uneste(xx,yy);
        }
    }
    g << ct << '\n' << Q.size() << '\n';

    while(not Q.empty())
    {
        g << v[Q.front()].x << " " << v[Q.front()].y << '\n';
        Q.pop();
    }
}

int main()
{
    read();
    sort(poz + 1,poz + m + 1,cmp);
    kruskal();
    return 0;
}