#include <fstream>
#include <vector>
#include <queue>
#define nmax 200005
#define inf 2e9
#define PII pair<int,int>

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

priority_queue <PII, vector<PII>, greater<PII> > h;
vector<PII> v[nmax];
int n,m,viz[nmax], t[nmax], cmin[nmax];

int prim(int s)
{
    int i, j, nod, vecin, cost, ct=0;

    for(i=1; i<=n; i++) cmin[i]=1e9;
    h.push({0,s});


    while(!h.empty())
    {
        nod = h.top().second;
        cost = h.top().first;
        h.pop();

        if (viz[nod]) continue;

        viz[nod]=1;
        ct+=cost;
        for(j=0; j<v[nod].size(); j++)
        {
            vecin = v[nod][j].second;
            cost = v[nod][j].first;
            if(!viz[vecin] && cost<cmin[vecin])
            {
                cmin[vecin]=cost;
                t[vecin]=nod;
                h.push({cost,vecin});
            }
        }
    }
    return ct;
}

int main()
{
    int a,b,c,i;

    f>>n>>m;
    for(i=1; i<=m; i++)
    {
        f>>a>>b>>c;
        v[a].push_back({c, b});
        v[b].push_back({c, a});
    }

    g<<prim(1)<<'\n'<<n-1<<'\n';
    for(i=2; i<=n; i++)
    {
        g<<i<<" "<<t[i]<<'\n';
    }
    return 0;
}