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

using namespace std;

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

const int NMAX=2e5+5;

#define cin fin
#define cout fout

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;
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        int x,y,cost;
        cin>>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])
        pq.push({1,i.first,i.second});
    int kon=1;
    while(kon<n)
    {
        elem p=pq.top();
        pq.pop();
        if(!viz[p.y])
        {
            viz[p.y]=true;
            ans[kon]=make_pair(p.x,p.y);
            kon++;
            s+=p.c;
            for(auto i:v[p.y])
            {
                if(!viz[i.first])
                    pq.push({p.y,i.first,i.second});
            }
        }
    }
    cout<<s<<"\n";
    cout<<kon-1<<"\n";
    for(i=1;i<=kon-1;i++)
        cout<<ans[i].first<<" "<<ans[i].second<<"\n";
    return 0;
}