#include<fstream>
#include<utility>
#include<vector>
#include<queue>
using namespace std;
struct triplet
{
    int x,y,c;
} aux;
triplet c_t(int x,int y,int c)
{
    triplet z;
    z.x=x,z.y=y,z.c=c;
    return z;
}
class compare_q
{
public:
    bool operator() (triplet a,triplet b)
    {
        return a.c>b.c;
    }
};
vector<pair<int,int> >v[200001];
priority_queue<triplet,vector<triplet>,compare_q> q;
queue<pair<int,int> > sol;
int n,m,i,x,y,c,nod;
long long sum;
bool viz[200001];
pair<int,int> aux2;
int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    fin>>n>>m;
    for(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));
        if(x==1)
            q.push(c_t(x,y,c));
        if(y==1)
            q.push(c_t(y,x,c));
    }
    viz[1]=1;
    while(!q.empty()&&nod<n-1)
    {
        aux=q.top();
        q.pop();
        while(viz[aux.y]==1)
        {
            aux=q.top();
            q.pop();
        }
        viz[aux.y]=1;
        sum+=aux.c;
        nod++;
        sol.push(make_pair(aux.x,aux.y));
        for(vector<pair<int,int> >::iterator j=v[aux.y].begin(); j!=v[aux.y].end(); j++)
        {
            if(viz[(*j).first]==0)
            q.push(c_t(aux.y,(*j).first,(*j).second));
        }
    }
    fout<<sum<<'\n'<<n-1<<'\n';
    while(!sol.empty())
    {
     aux2=sol.front();
     sol.pop();
     fout<<aux2.first<<' '<<aux2.second<<'\n';
    }

}