#include <bits/stdc++.h>
#define pii pair<int,int>

using namespace std;

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

struct drumuri{
    int node, cost, t;
};

struct compare{
    bool operator()(drumuri a,drumuri b){
        return a.cost>b.cost;
    }
};

int n,m,x,y,z,viz[200200],tata[200200],s;
vector <drumuri> edges[200200];
priority_queue <drumuri, vector<drumuri>, compare> pq;

void prim()
{
    pq.push({1,0,0});
    while(!pq.empty())
    {
        drumuri x=pq.top(); pq.pop();
        if(viz[x.node]==0)
        {
            viz[x.node]=1;
            s+=x.cost, tata[x.node]=x.t;
            for(auto y:edges[x.node])
                if(viz[y.node]==0)
                    pq.push({y.node,y.cost,x.node});
        }
    }
}

int32_t main()
{
    f>>n>>m;
    for(int i=1; i<=m; i++)
        f>>x>>y>>z, edges[x].push_back({y,z,0}), edges[y].push_back({x,z,0});
    prim();
    g<<s<<'\n'<<n-1<<'\n';
    for(int i=2; i<=n; i++)
        g<<i<<' '<<tata[i]<<'\n';
    return 0;
}