#include <bits/stdc++.h>


// Algoritmul lui PRIM

using namespace std;



ifstream f("apm.in");
ofstream g("apm.out");

vector< pair<int,int > > v[200100];
priority_queue <  pair <int, pair<int,int > >, vector <pair <int, pair<int,int > > >, greater <pair <int, pair<int,int > > >   > h;





int n,m,x,k,y,c,nod,i,ct,t[200100];

struct
{
    int X,Y;
}V[400100];

int main()
{

    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        v[x].push_back({c,y});
        v[y].push_back({c,x});
    }


    h.push({0,{1,1}});

    while(!h.empty())
    {
        nod = h.top().second.second;
        if(t[nod]==0)
        {
            t[nod]=1;
            ct+=h.top().first;

            k++;
            V[k].X = h.top().second.first;
            V[k].Y = h.top().second.second;

            h.pop();



            for(i=0;i<v[nod].size();i++)
            {
                if(t[v[nod][i].second]==0)
                h.push({v[nod][i].first,{nod,v[nod][i].second}});
            }

        }
        else h.pop();
    }

    g<<ct<<'\n';
    g<<n-1<<'\n';
    for(i=2;i<=n;i++)
        g<<V[i].X<<" "<<V[i].Y<<'\n';
    return 0;
}