#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>

using namespace std;
priority_queue <pair<pair<int,int>,int> >q;
vector <pair<int,int> >G[200005];
int m,n,isInApm[200005],vTati[200005];
void citire()
{
    int aux1,aux2,aux3;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%d",&aux1,&aux2,&aux3);
        G[aux1].push_back(make_pair(-aux3,aux2));
        G[aux2].push_back(make_pair(-aux3,aux1));
    }
}
void apm(int nod)
{
    int cost=0;
    int cnt=1;
    isInApm[nod]=1;
    vTati[nod]=0;
    for(auto it:G[nod])
    {
        q.push(make_pair(it,nod));
    }
    while(cnt!=n)
    {
        nod=q.top().first.second;
        isInApm[nod]=1;
        vTati[nod]=q.top().second;
        cnt++;
        cost-=q.top().first.first;
        q.pop();

        for(auto it:G[nod])
        {
            if(!isInApm[it.second])
            {
                q.push(make_pair(it,nod));
            }
        }
    }
    printf("%d\n%d\n",cost,n-1);
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire();
    apm(1);
    for(int i=2;i<=n;i++)
    {
        printf("%d %d\n",i,vTati[i]);
    }
    return 0;
}