#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>

#define maxN 200005

using namespace std;

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

int n,m;
vector < pair <int,int> > v[maxN];
bool used[maxN];
int d[maxN], t[maxN];

struct cmp
{
    bool operator()(const pair <int,int> &left, const pair <int,int> &right) const
   {
       return left.second > right.second;
   }
};

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

priority_queue < pair<int,int>, vector < pair <int,int> >, cmp > Q;

void Prim()
{
    int nr=n, costAPM=0;
    fill(d+2,d+n+1,1<<30);
    Q.push(make_pair(1,0));
    used[0]=1;
    while (nr)
    {
        int x=0;
        while (used[x]) {
            x=Q.top().first;
            Q.pop();
        }
        used[x]=1;
        costAPM+=d[x];
        nr--;
        for (int i=0; i<v[x].size(); ++i)
        {
            pair <int,int> nod=v[x][i];
            if (nod.second<d[nod.first]&&!used[nod.first]) {
                t[nod.first]=x;
                d[nod.first]=nod.second;
                Q.push(make_pair(nod.first,nod.second));
            }
        }
    }
    fout<<costAPM<<'\n'<<n-1<<'\n';
    for (int i=2; i<=n; ++i) fout<<i<<' '<<t[i]<<'\n';
}

int main()
{
    citire();
    Prim();
    return 0;
}