#include <fstream>
#include <vector>

#define maxn 2 * 100010
#define inf 2e9
#define pb push_back
#define mp make_pair

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int n, m, pos[maxn], d[maxn], t[maxn], h[3 * maxn], hs, tcost;
vector <pair <int, int> > g[maxn], ans;

int father(int node)
{
    return node >> 1;
}

int lson(int node)
{
    return node << 1;
}

int rson(int node)
{
    return (node << 1) + 1;
}

void addtoApm(int node)
{
    vector <pair <int, int > > :: iterator it;
    for (it = g[node].begin(); it != g[node].end(); ++it)
    {
        int v = it -> first;
        int c = it -> second;
        if (d[v] > c)
        {
            d[v] = c;
            t[v] = node;
        }
    }
}

void percolate(int k)
{
    while (k > 1 && d[h[father(k)]] > d[h[k]])
    {
        swap(h[father(k)], h[k]);
        swap(pos[h[father(k)]], pos[h[k]]);
        k = father(k);
    }
}

void addtoHeap(int node)
{
    h[++hs] = node;
    pos[node] = hs;
    percolate(hs);
}

void sift(int k)
{
    int son = 0;
    do
    {
        son = 0;
        if (lson(k) <= hs)
        {
            son = lson(k);
            if (rson(k) <= hs && h[rson(k)] < h[son])
                son = rson(k);
            if (d[h[son]] > d[h[k]])
                son = 0;
        }
        if (son)
        {
            swap(h[son], h[k]);
            swap(pos[h[son]], pos[h[k]]);
            k = son;
        }
    } while (son);
}

int getBest()
{
    int node = h[1];
    swap(h[1], h[hs]);
    swap(pos[h[1]], pos[h[hs]]);
    --hs;
    sift(1);
    pos[node] = 0;
    return node;
}

void algPrim()
{
    vector <pair <int, int> > :: iterator it;
    addtoApm(1);
    for (int i = 2; i <= n; i++)
        addtoHeap(i);
    for (int i = 2; i <= n; i++)
    {
        int best = getBest();
        addtoApm(best);
        tcost += d[best];
        ans.pb(mp(best, t[best]));
        for (it = g[best].begin(); it != g[best].end(); ++it)
        {
            int v = it -> first;
            if (pos[v])
                percolate(pos[v]);
        }
    }
    fout << tcost << '\n';
    fout << n - 1 << '\n';
    for (it = ans.begin(); it != ans.end(); ++it)
        fout << it -> first << " " << it -> second << '\n';
}

int main()
{
    fin >> n >> m;
    for (int a, b, c; m; --m)
    {
        fin >> a >> b >> c;
        g[a].pb(mp(b, c));
        g[b].pb(mp(a, c));
    }
    for (int i = 2; i <= n; i++)
        d[i] = inf;
    algPrim();
    return 0;
}