#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

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

const int NMAX=2e5+5;

struct elem{
    int x;
    int y;
    int c;
    bool operator <(const elem &other) const
    {
        return c>other.c;
    }
};

priority_queue<elem>pq;

vector<pair<int,int>>v[NMAX];
pair<int,int>ans[NMAX];

bool viz[NMAX];

int main()
{
    int n,m,i,j;
    long long s=0;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        int x,y,cost;
        fin>>x>>y>>cost;
        v[x].push_back(make_pair(y,cost));
        v[y].push_back(make_pair(x,cost));
    }
    viz[1]=true;
    for(auto i:v[1])
    {
        elem aux;
        aux.x=1;
        aux.y=i.first;
        aux.c=i.second;
        pq.push(aux);
    }
    j=1;
    while(j<n)
    {
        elem p=pq.top();
        pq.pop();
        if(!viz[p.y])
        {
            s+=p.c;
            ans[j].first=p.x;
            ans[j].second=p.y;
            j++;
            viz[p.y]=true;
            for(auto i:v[p.y])
            {
                if(!viz[i.first])
                {
                    elem aux;
                    aux.x=p.y;
                    aux.y=i.first;
                    aux.c=i.second;
                    pq.push(aux);
                }
            }
        }
    }
    fout<<s<<"\n";
    fout<<n-1<<"\n";
    for(i=1;i<n;i++)
        fout<<ans[i].first<<" "<<ans[i].second<<"\n";
    return 0;
}