#include <fstream>
#include <vector>
#include <queue>
#include <functional>

#define DoiLa32 2000000000

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int n,m,i,x,y,c,sum,nod,nr,tati[500010],dismin[500010];
bool viz_in_ar[500010];

priority_queue< pair<int, int > , vector< pair<int, int > > , greater< pair<int, int > > > qu;
vector< pair<int, int > > l[500010];

void dijkstrakindof()
{
    qu.push({0,1});
    viz_in_ar[1]=1;

    while(!qu.empty())
    {
        nod=qu.top().second;
        //++nr;
        qu.pop();
        viz_in_ar[nod]=1;
        for(int i=0;i<l[nod].size();++i)
        {
            if(viz_in_ar[l[nod][i].first]==0 && l[nod][i].second<dismin[l[nod][i].first])
            {
                if(dismin[l[nod][i].first]==DoiLa32)
                    sum+=l[nod][i].second;
                else
                {
                    sum-=dismin[l[nod][i].first];
                    sum+=l[nod][i].second;
                }
                tati[l[nod][i].first]=nod;
                dismin[l[nod][i].first]=l[nod][i].second;
                qu.push({l[nod][i].second,l[nod][i].first});
            }
        }
    }
}

int main()
{
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>x>>y>>c;
        l[x].push_back({y,c});
        l[y].push_back({x,c});
    }

    for(i=2;i<=n;++i)
        dismin[i]=DoiLa32;

    dijkstrakindof();
    i=2;
    fout<<sum<<"\n";
    fout<<n-1<<"\n";
    while(i<=n && tati[i])
    {
        fout<<i<<" "<<tati[i]<<"\n";;
        ++i;
    }

    return 0;
}