#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#define MAX_N 200001
#define inf 0x3f3f3f3f
using namespace std;
int h[MAX_N],n,m,i,nr,nod,S,t[MAX_N],d[MAX_N],pos[MAX_N];
vector< pair<int,int> > a[MAX_N],sol;
void swapp(int i, int j)
{
    swap(h[i],h[j]);
    pos[h[i]]=i;
    pos[h[j]]=j;
}
void push(int x)
{
    while(x/2&&d[h[x]]<d[h[x/2]])
        swapp(x,x/2),x/=2;
}
void pop(int x, int m)
{
    int y=0;
    while(x!=y)
    {
        y=x;
        if(y*2<=m&&d[h[x]]>d[h[y*2]]) x = 2*y;
        if(y*2+1<=m&&d[h[x]]>d[h[y*2+1]]) x = 2*y+1;
        swapp(x,y);
    }
}
int Ext()
{
    int v=h[1];
    swapp(1,nr);
    nr--;
    pop(1,nr);
    pos[v]=0;
    return v;
}
int main()
{
    ifstream f("apm.in");
    f>>n>>m;
    int x,y,c;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        a[x].push_back(make_pair(y,c));
        a[y].push_back(make_pair(x,c));
    }
    f.close();
    nr =0;
    for(i=2;i<=n;i++)d[i]=inf;
    for(i=0;i<a[1].size();i++)
    {
        d[a[1][i].first]=a[1][i].second;
        t[a[1][i].first]=1;
    }
    for(int i=2;i<=n;i++)
    {
        h[++nr]=i;
        pos[i]=nr;
        push(nr);
    }
    while(nr)
    {
        nod=Ext();
        S+=d[nod];
        sol.push_back(make_pair(t[nod],nod));
        for(i=0;i<a[nod].size();i++)
        {
            c=a[nod][i].second;
            if(d[a[nod][i].first]>c)
            {
                d[a[nod][i].first]=c;
                t[a[nod][i].first]=nod;
                push(pos[a[nod][i].first]);
            }
        }
    }
    ofstream g("apm.out");
    g<<S<<"\n"<<sol.size()<<'\n';
    for(i=0;i<sol.size();i++)
        g<<sol[i].first<<" "<<sol[i].second<<"\n";
    g.close();
    return 0;
}