#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
#define NMAX 200005
#define MAx 99999999
using namespace std;

vector <pair<int,int> > G[NMAX];
vector <pair<int,int> > ::iterator itG;
priority_queue < pair<int,int> > q;
int vTati[NMAX],dp[NMAX],viz[NMAX];
int n,m;

void citire()
{
    scanf("%d%d",&n,&m);
    int x,y,z;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        G[x].push_back(make_pair(z,y));
        G[y].push_back(make_pair(z,x));
    }
    for(int i=1;i<=n;i++)
        dp[i]=MAx;
}

void parcurgereListaDeVecini(int varf)
{
    for(itG=G[varf].begin();itG!=G[varf].end();itG++)
    {
        if(!viz[itG->second])
        {
            if(itG->first<dp[itG->second])
            {
                //viz[itG->second]=1;
                dp[itG->second]=itG->first;
                //cout<<varf<<"  "<<itG->second<<" "<<itG->first<<"\n";
                q.push(make_pair((-1)*(itG->first),itG->second));
                vTati[itG->second]=varf;
            }
        }
    }
}

void createArbore()
{
    q.push(make_pair(0,1));
    vTati[1]=0;
    viz[1]=1;
    dp[1]=0;
    int x;
    while(!q.empty())
    {
        x=q.top().second;
        //cout<<q.top().first<<" "<<q.top().second<<"\n";
        q.pop();
        viz[x]=1;
        parcurgereListaDeVecini(x);
        //cout<<q.top().first<<" "<<q.top().second<<"\n";
        //cout<<endl;
    }
}

void printArbore()
{
    int s=0;
    for(int i=2;i<=n;i++)
    s+=dp[i];
    printf("%d\n%d\n",s,n-1);
    for(int i=2;i<=n;i++)
        printf("%d %d\n",i,vTati[i]);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire();
    createArbore();
    printArbore();

    return 0;
}