#include <iostream>
#include <fstream>
#include <queue>
#define INF 1000000
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,x,y,cost,viz[200001],d[200001],tat[200001],s,nr;
struct imp
{
    int a,cost;
};
vector <vector <imp>> v(200001);
auto cmp=[](imp a,imp b){if (a.cost>b.cost) return 1;else return 0;};
priority_queue <imp ,vector <imp>,decltype(cmp)> q(cmp);
int main()
{
    f>>n>>m;
    for (int i=1; i<=m; i++)
    {
        f>>x>>y>>cost;
        imp ins;
        ins.a=y;
        ins.cost=cost;
        v[x].push_back(ins);
        ins.a=x;
        v[y].push_back(ins);
    }
    for (int i=1; i<=n; i++)
    {
        d[i]=INF;
    }
    imp ins;
    ins.a=1;
    ins.cost=0;
    q.push(ins);
    viz[1]=1;
    d[1]=0;
    tat[1]=0;
    while (!q.empty())
    {
        imp t=q.top();
       // cout<<t.a<<' '<<t.cost<<'\n'<<'\n';
        viz[t.a]=1;
        q.pop();
        for (int j=0; j<v[t.a].size(); j++)
        {
            int node=v[t.a][j].a;
            if (d[node]>v[t.a][j].cost && viz[node]==0)
            {
                //cout<<t.a<<' '<<node<<'\n';
                d[node]=v[t.a][j].cost;
                tat[node]=t.a;
                    imp ins;
                    ins.a=node;
                    ins.cost=d[node];
                    q.push(ins);
                   // cout<<ins.a<<' '<<ins.cost<<'\n';
            }
        }
    }
    for (int i=1; i<=n; i++)
    {
        //cout<<d[i]<<' ';
        s+=d[i];
        if (tat[i]!=0)
            nr++;
    }
    g<<s<<'\n'<<nr<<'\n';
    for (int i=2; i<=n; i++)
    {
        if (tat[i]!=0)
        g<<i<<' '<<tat[i]<<'\n';
    }
    return 0;
}