#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define mp make_pair
using namespace std;


ifstream fin("apm.in");
ofstream fout("apm.out");
pair <int,int> sol[200009];
vector <pair <int,int> > v[200009];
priority_queue <pair <int,pair <int,int > >,vector <pair <int,pair <int,int > > >, greater <pair <int,pair <int,int> > > > h ;
int n,m,x,y,c,t[200009],i,sm;
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        v[x].pb(mp(c,y));
        v[y].pb(mp(c,x));
    }
    int  L=0;
    h.push(mp(0,mp(1,1)));
    while(!h.empty())
    {
        int nod=h.top().s.s;
        if(t[nod]==0)
        {
            t[nod]=h.top().s.f;
            sol[++L].s=nod,sol[L].f=t[nod];
            sm+=h.top().f;
            h.pop();
            for(i=0;i<v[nod].size();i++)
            {
                if(t[v[nod][i].s]==0)
                    h.push(mp(v[nod][i].f,mp(nod,v[nod][i].s)));
            }
        }
        else
            h.pop();
    }
    fout<<sm<<'\n'<<n-1<<'\n';
    for(i=2;i<=n;i++)
        fout<<sol[i].f<<" "<<sol[i].s<<'\n';
	return 0;
}