#include <bits/stdc++.h>
#define BIT(x) (1<<(x))
#define left(x) ((x)<<1)
#define right(x) (((x)<<1)|1)
#define top(x) ((x)>>1)
#define inf 0x3f3f3f3f

using namespace std;

const int maxn = 200010;
int n, m;

int dmin;
vector< pair<int, int> > rez;
vector< pair<int, int> > v[maxn];
int t[maxn];
int d[maxn];
int h[BIT(19)+10];
int p[maxn];
int hs;

int heap_goup(int pos)
{
    while(d[h[top(pos)]] > d[h[pos]])
    {
        swap(p[h[top(pos)]], p[h[pos]]);
        swap(h[top(pos)], h[pos]);
        pos = top(pos);
    }
    return pos;
}

int heap_godown(int pos)
{
    int pmin;
    while(1)
    {
        if(d[h[left(pos)]] <= d[h[right(pos)]] || left(pos) == hs)
            pmin = left(pos);
        else pmin = right(pos);
        if(pmin > hs) break;
        if(d[h[pos]] > d[h[pmin]])
        {
            swap(p[h[pmin]], p[h[pos]]);
            swap(h[pos], h[pmin]);
            pos = pmin;
        }
        else break;
    }
    return pos;
}

void heap_push(int nr)
{
    h[++hs] = nr;
    p[nr] = hs;
    heap_goup(hs);
}

int heap_pop(int pos)
{
    int ret = h[pos];
    if(pos == hs)
    {
        p[h[hs]] = 0;
        h[hs] = 0;
        hs--;
    }
    else
    {
        p[h[hs]] = pos;
        p[h[pos]] = 0;
        swap(h[pos], h[hs]);
        h[hs] = 0;
        hs--;
        pos = heap_goup(pos);
        heap_godown(pos);
    }
    return ret;
}

int main()
{
    int a, b, c;
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i++)
    {
        scanf("%d%d%d", &a, &b, &c);
        v[a].push_back(make_pair(b, c));
        v[b].push_back(make_pair(a, c));
    }
    memset(d, 0x3f, sizeof(d[0]) * (n + 1));
    d[0] = -inf;
    d[1] = 0;
    for(int i = 0; i < v[1].size(); i++)
    {
        d[v[1][i].first] = v[1][i].second;
        t[v[1][i].first] = 1;
    }
    for(int i = 2; i <= n; i++)
        heap_push(i);
    for(int i = 1; i < n; i++)
    {
        int nod = heap_pop(1);

        dmin += d[nod];
        d[nod] = 0;
        rez.push_back(make_pair(nod, t[nod]));

        for(int i = 0; i < v[nod].size(); i++)
        {
            if(p[v[nod][i].first] && v[nod][i].second < d[v[nod][i].first])
            {
                heap_pop(p[v[nod][i].first]);
                t[v[nod][i].first] = nod;
                d[v[nod][i].first] = v[nod][i].second;
                heap_push(v[nod][i].first);
            }
        }
    }
    printf("%d\n%d\n", dmin, n - 1);
    for(int i = 0; i < n - 1; i++)
    {
        printf("%d %d\n", rez[i].first, rez[i].second);
    }
    return 0;
}