#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#define NMAX 200005
#define INF 123123123
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");

struct edge
{
    int vf,c;
};
vector <edge> G[NMAX];

bool comp(edge a, edge b)
{
    return a.c <= b.c ;
}

void citire();
void prim();
struct muchie
{
    int x,y;
    int c;
    friend bool operator < (muchie m1,muchie m2);
};
priority_queue<muchie> H;
muchie a[NMAX];
int m,i,n,nr,S,j,t;
bool uz[NMAX];
bool operator < (muchie m1,muchie m2)
{
    return m1.c > m2.c;
}

int main()
{
    citire();
    prim();
    cout<<S<<'\n'<<n-1<<'\n';
    for(i=1;i<n;i++)
    {
        cout<<a[i].x<<' '<<a[i].y<<'\n';
    }
    return 0;
}
void citire()
{
    int i,x,y,cost,m;
    edge p;
    cin>>n>>m;
    for(i=0; i<m; i++)
    {
        cin>>x>>y>>cost;
        p.vf=y;
        p.c=cost;
        G[x].push_back(p);
        p.vf=x;
        p.c=cost;
        G[y].push_back(p);
    }
}
void prim()
{
    int start=1,i,j,vfmin,x,costmin;
    uz[start]=1;
    muchie m;
    for(i=0; i<G[start].size(); i++)
    {
        m.y=start;
        m.x=G[start][i].vf;
        m.c=G[start][i].c;
        H.push(m);
    }
    for(i=1; i<n;)
    {
        m=H.top();
        H.pop();
        //aleg un varf neselectat pentru care cmin este minim
        if(uz[m.x]==0)
        {
            uz[m.x]=1;

            S+=m.c;
            a[i]=m;
            i++;
            int vf=m.x;
            muchie mm;
        for(int k=0;k<G[vf].size();k++)
        {
            if(uz[G[vf][k].vf]==0)
            {
                mm.x=G[vf][k].vf;
                mm.y=vf;
                mm.c=G[vf][k].c;
                H.push(mm);
            }
        }
        }


    }
}