#include <cstdio>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;
const int N=200001;
int n,m,cost;
struct heap
{
    int nod,cost;
};
int apm[N];
vector<heap>H[N];
vector<heap>::iterator it;
bitset<N>uz;
struct cmp
{
    bool operator()(const heap &a,const heap &b)
    {
        return a.cost>b.cost;
    }
};
priority_queue<heap,vector<heap>,cmp>Q;
void read()
{
    scanf("%d%d",&n,&m);
    int a;heap b;
    while(m--)
    {
        scanf("%d%d%d",&a,&b.nod,&b.cost);
        H[a].push_back(b);
        swap(a,b.nod);
        H[a].push_back(b);
    }
}
void prim()
{
    heap step;
    uz[1]=1;apm[1]=1;
    for(it=H[1].begin();it!=H[1].end();it++)
    {
        Q.push(*it);
    }
    for(int i=2;i<=n;++i)
    {
        while(uz[Q.top().nod]==1) Q.pop();
        step=Q.top();
        Q.pop();
        uz[step.nod]=1;
        apm[i]=step.nod;
        cost+=step.cost;
        for(it=H[step.nod].begin();it!=H[step.nod].end();it++)
        {
            if(uz[it->nod]==0) Q.push(*it);
        }
    }
}
void write()
{
    printf("%d\n%d\n",cost,n-1);
    for(int i=1;i<n;i++) printf("%d %d\n",apm[i],apm[i+1]);
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    read();
    prim();
    write();
}