#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
vector <pair<int,int> >G[200005];
priority_queue<pair <int,int> > apm;
int n,m;
int vDistante[200005];
bool vViz[200005];
int 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(aux2,aux3));
        G[aux2].push_back(make_pair(aux1,aux3));
    }
    for(int i=1; i<=n; i++)
        vDistante[i]=0x3f3f3f;
}
void parcurgVecinii(int nod)
{
    vViz[nod]=true;
    vector <pair<int,int> >::iterator IT;
    for(IT=G[nod].begin(); IT!=G[nod].end(); IT++)
    {
        if(!vViz[IT->first])
        {
            if(vDistante[IT->first]>IT->second)
            {
                vDistante[IT->first]=IT->second;
                vTati[IT->first]=nod;
                apm.push(make_pair(-IT->second,IT->first));
            }
        }

    }
}
void solve()
{
    int nod;
    apm.push(make_pair(0,1));
    vDistante[1]=0;
    while(!apm.empty())
    {
        nod=apm.top().second;
        apm.pop();
        if(!vViz[nod])
        {
            parcurgVecinii(nod);
        }
    }
}
void print()
{
    int sum=0;
    for(int i=1; i<=n; i++)
        sum+=vDistante[i];
    printf("%d\n%d\n",sum,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();
    solve();
    print();
    return 0;
}