#include <iostream>
#include <fstream>
#include <bitset>
#include <queue>
#include <vector>

#define DN 200005
#define mp make_pair
#define pb push_back
#define per pair<int,int>
#define x first
#define y second
#define st pair < int , per >
using namespace std;


priority_queue < st  , vector < st > , greater < st > > q;
vector < per > list[DN],rez;
bitset < DN > viz;
int apm;

void solve()
{
    q.push(mp(0,mp(1,0)));

    for(int nod,C,prev_nod;q.size();){

        st p = q.top();
        nod = p.y.x;
        prev_nod = p.y.y;
        C = p.x;
        q.pop();

        if(!viz[nod]){

            viz[ nod ] = true;
            apm+=C;
            rez.pb(mp(prev_nod,nod));
            for(int i=0;i<list[nod].size();++i){

                int next_nod = list[nod][i].x , cost = list[nod][i].y;

                if(!viz[ next_nod ])
                    q.push( mp( cost , mp(next_nod,nod) ));
            }
        }
    }
}

int main()
{
    int n,m;
    ifstream f("apm.in");
    ofstream g("apm.out");
    f>>n>>m;
    for(;m--;)
    {
        int a,b,c;
        f>>a>>b>>c;
        list[a].pb(mp(b,c));
        list[b].pb(mp(a,c));
    }
    solve();
    g<<apm<<"\n"<<rez.size()-1<<"\n";
    for(int i=1;i<rez.size();++i)
        g<<rez[i].x<<" "<<rez[i].y<<"\n";
    return 0;
}