#include <vector>
#include <fstream>
#include <queue>
#include <algorithm>

using namespace std;

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

const int inf=10000, N=1000000;

int n, d[100000], cost,  pred[100000], m;

bool sel[100000];

vector <pair <int, int> > a[N];
priority_queue <pair <int, int> > h;

void prim ()
{
    int x,y,c;
    for (int i=2; i<=n; i++)
    {
        d[i]=inf;
    }


    h.push (make_pair (-d[1], 1));

    while (!h.empty ())
    {
        while (!h.empty () && sel [h.top ().second])
        {
            h.pop();
        }
        if (h.empty()) return;

        x=h.top().second;

        cost+=d[x];

        sel[x]=true;

        h.pop();

        for (int i=0; i<a[x].size(); i++)
        {
            y = a[x][i].first;
            c = a[x][i].second;
            if (c < d[y] && !sel[y])
            {
                d[y] = c;
                pred [y] = x;
                h.push (make_pair (-d[y], y));
            }
        }
    }
}

int main()
{
    int x,y, c;

    in>>n>>m;

    for(int i=1;i<=m;i++)
    {
        in>>x>>y>>c;
        a[x].push_back (make_pair  (y, c));
        a[y].push_back (make_pair (x, c));
    }

    prim();

    out<<cost<<"\n"<<n-1<<"\n";
    for (int i=2; i<=n; i++)
    {
        out<<i<<" "<<pred[i]<<"\n";
    }


    return 0;
}