#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define NMAX 200010
#define INF 0x3f3f3f3f

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct NodCost {
  int nod1,nod2, cost;
  bool operator < (const NodCost& other) const {
    return cost > other.cost;
  }
};
struct NodCostGraf{
    int nod,cost1;
};
vector<NodCostGraf> G[NMAX],G1[NMAX];
long long int ap[NMAX];
priority_queue<NodCost> q;
int n,cost;
int main()
{
    int n,a,b,i,c,m;
    fin>>n>>m;
    for (i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        G[a].push_back({b,c});
        G[b].push_back({a,c});
    }
    ap[1]=1;
    for (auto i:G[1])
        q.push({1,i.nod,i.cost1});
    int nr=1;
    while (!q.empty() && nr<n){
            int x1=q.top().nod1;
            int x2=q.top().nod2;
            int y=q.top().cost;
            q.pop();
        if (ap[x2]==0){
                cost+=y;
            ap[x2]=1;
            nr++;
            G1[x1].push_back({x2,y});
            for (auto i : G[x2])
            {
                if (ap[i.nod]==0)
                {
                    q.push({x2,i.nod,i.cost1});
                }
            }

        }
    }
    fout<<cost<<"\n";
    fout<<n-1<<"\n";
    for (i=1;i<=n;i++)
    {
        for (auto j :G1[i])
        {
            fout<<i<<" "<<j.nod<<"\n";
        }
    }
        fin.close();
        fout.close();
    return 0;
}