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

#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];

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));
    }
}

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

    fout<<costAPM<<'\n'<<n-1<<'\n';
    for (int i=2; i<=n; ++i)
        fout<<i<<' '<<t[i]<<'\n';
}


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