#include <iostream>
#include <fstream>
#include <set>
#include <vector>
#define nmx 200001
#define mmx 400001
#define inf 1073741823
using namespace std;

int d[nmx],t[nmx],n,m;
bool viz[nmx];
vector <pair<int,int> > lv[nmx];
set <pair<int,int> >s;

int main()
{
    ifstream fin("apm.in");
    fin>>n>>m;
    int i,x,y,cost,nodc;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>cost;
        lv[x].push_back(make_pair(y,cost));
        lv[y].push_back(make_pair(x,cost));
    }
    for(i=1;i<=n;i++)d[i]=inf;
    s.insert(make_pair(0,1));
    d[1]=0;
    while(!s.empty())
    {
        nodc=s.begin()->second;
        s.erase(s.begin());
        viz[nodc]=1;
        for(auto&a:lv[nodc])
        {
            y=a.first;
            cost=a.second;
            if(!viz[y]&&cost<d[y])
            {
                s.erase(make_pair(d[y],y));
                d[y]=cost;
                t[y]=nodc;
                s.insert(make_pair(d[y],y));
            }
        }
    }
    int sum=0;
    for(i=1;i<=n;i++)
        sum+=d[i];
    ofstream fout("apm.out");
    fout<<sum<<"\n";
    for(i=2;i<=n;i++)
        fout<<t[i]<<" "<<i<<"\n";
    return 0;
}