#include <cstdio>
#include <vector>
#include <queue>
#include <utility>
#define nmax 100005
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
using namespace std;
FILE *fin=fopen("apm.in","r");
FILE *fout=fopen("apm.out","w");
int n, m;
int x, y, c;
int ans;
vector<pii>mans;
priority_queue<pair<int,pii>, vector<pair<int,pii>>, greater<pair<int,pii>> >hp;
int tata[nmax];
int h[nmax];
void unionn(int x, int y);
int findd(int x);
int main()
{
    fscanf(fin,"%d %d",&n,&m);
    for (int i=1;i<=m;++i)
    {
        fscanf(fin,"%d %d %d",&x,&y,&c);
        hp.push(mp(c, mp(x, y)));
    }
    int nr = 0;
    while (nr<n && !hp.empty())
    {
        pair<int,pii>act = hp.top();
        hp.pop();
        int m1 = findd(act.second.first);
        int m2 = findd(act.second.second);
        if (m1 == m2)
        {
            continue;
        }
        ans += act.first;
        unionn(m1,m2);
        mans.pb(mp(act.second.first, act.second.second));
    }
    fprintf(fout,"%d\n",ans);
    fprintf(fout,"%d\n",mans.size());
    for (int i=0;i<mans.size();++i)
    {
        fprintf(fout,"%d %d\n",mans[i].first, mans[i].second);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}
void unionn(int x, int y)
{
    if (h[x]>h[y])
    {
        tata[y] = x;
    }
    else if (h[x]<h[y])
    {
        tata[x] = y;
    }
    else
    {
        tata[y] = x;
        ++h[x];
    }
}
int findd(int x)
{
    int cx = x;
    while (tata[x])
    {
        x = tata[x];
    }
    if (x!=cx)
    {
        while (tata[cx])
        {
            int t = tata[cx];
            tata[cx] = x;
            cx = t;
        }
    }
    return x;
}