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

using namespace std;
#define NMAX 200005
#define INF (1<<30)

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

struct elem{
    int nod,cost;
};

int n, m, costT;
vector <elem> g[NMAX];
vector <int> sol;

bool viz[NMAX];
int c[NMAX];
int leg[NMAX];

class cmp{
public:
    bool operator()(int &a, int &b){
        return c[a]>c[b];
    };
};
priority_queue <int, vector<int>, cmp > q;


void citire()
{
    int x,y,c;
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y >>c;
        g[x].push_back({y,c});
        g[y].push_back({x,c});
    }
}

void apm()
{

    int nr_vf=0, v, k, v1;
    c[1] = 0;q.push(1);
    while(nr_vf != n){
        v = q.top();
        q.pop();
        if(viz[v] == 1) continue;

        sol.push_back(v);
        nr_vf++; viz[v] = 1;costT+=c[v];

        k=g[v].size();
        for(int i = 0; i < k;i++)
        {
            v1=g[v][i].nod;
            if(viz[v1] == 0 && c[v1] > g[v][i].cost)
            {
                c[v1]=g[v][i].cost;
                leg[v1] = v;
                q.push(v1);

            }
        }
    }
}
int main()
{
    citire();
    for(int i = 1; i <= n; i++)
        c[i] = INF;
    apm();
    fout << costT <<'\n' << n-1<<'\n';
    int k = sol.size();
    for(int i = 1 ;i < k; i++)
        fout << sol[i] << ' '<< leg[sol[i]]<<"\n";

    return 0;
}