#include <bits/stdc++.h>
#define nm 200005
#define nmm nm*(nm-1)/2
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muc{int x,y,c;};
int tata[nm], h[nm];
vector <muc> q;
vector < pair<int,int> > sol;
void unire(int a,int b)
{
    if(h[a]>h[b]) tata[b]=a;
    else tata[a]=b;
    if(h[a]==h[b]) h[b]++;
}
int gasire(int a)
{
    int r=a;
    while(tata[r]) r=tata[r];
    return r;
}
bool cmp (muc a, muc b) {return a.c<b.c;};
int main()
{
    muc temp;
    int i,n,m,tc=0,x,y,c;
    fin>>n>>m;
    for(i=0;i<m;i++)
        {fin>>temp.x>>temp.y>>temp.c;
        q.push_back(temp);}
    sort(q.begin(),q.end(),cmp);
    for(i=0; i<q.size(); i++)
    {
        x=q[i].x;
        y=q[i].y;
        c=q[i].c;
        int r1=gasire(x), r2=gasire(y);
        if(r1!=r2)
        {
            sol.push_back(make_pair(x,y));
            tc+=c;
            unire(r1,r2);
        }
    }
    fout<<tc;
    fout<<"\n"<<n-1<<"\n";
    for(i=0;i<n-1;i++)
        fout<<sol[i].first<<" "<<sol[i].second<<"\n";
}