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

using namespace std;

int n,m,viz[200005],cost,nsol;
vector<pair<int,int> >g[200005];
vector<pair<int,int> >sol;
struct muchie
{
    int x,y,c;
    bool operator<(muchie b) const
    {
        return c>b.c;
    }
};
priority_queue<muchie,vector<muchie>>q;

void citire()
{
    ifstream fin("apm.in");
    fin>>n>>m;
    int x,y,c;
    for(int i=0;i<m;i++)
    {
        fin>>x>>y>>c;
        g[x].push_back(make_pair(y,c));
        g[y].push_back(make_pair(x,c));
    }
}

void prim()
{
    viz[1]=1;
    int nr=g[1].size();
    for(int i=0;i<nr;i++)
    {
        muchie nou;
        nou.x=1;
        nou.y=g[1][i].first;
        nou.c=g[1][i].second;
        q.push(nou);
    }
    for(int k=0;k<n-1;k++)
    {
        int nod=0;
        while(!nod&&!q.empty())
        {
            muchie nou=q.top();
            if(!viz[nou.x])
            {
                sol.push_back(make_pair(nou.x,nou.y));
                viz[nou.x]=1;
                nod=nou.x;
                cost+=nou.c;
            }
            if(!viz[nou.y])
            {
                sol.push_back(make_pair(nou.x,nou.y));
                viz[nou.y]=1;
                nod=nou.y;
                cost+=nou.c;
            }
            q.pop();
        }
        nr=g[nod].size();
        for(int i=0;i<nr;i++)
        {
            muchie nou;
            nou.x=nod;
            nou.y=g[nod][i].first;
            nou.c=g[nod][i].second;
            q.push(nou);
        }
    }
}

void afisare()
{
    ofstream fout("apm.out");
    fout<<cost<<"\n"<<n-1<<"\n";
    for(int i=0;i<n-1;i++)
        fout<<sol[i].first<<" "<<sol[i].second<<"\n";
}

int main()
{
    citire();
    prim();
    afisare();
    return 0;
}