#include <bits/stdc++.h>
#define secv pair <int , pair <int , int > >
#define ll long long
using namespace std ;
ifstream f ("apm.in") ;
ofstream g ("apm.out") ;
vector <pair <int , int > > v[200010];
priority_queue < secv , vector < secv > , greater <secv> > h;
struct q
{
    int st;
    int dr;
}sol[200010];
int N , M , x , y , cost;
int t[200005];
int cnt = 0;
ll Cost = 0 ;
void Solve ()
{
    h.push( make_pair(0 , make_pair(1,1))) ;
    while (!h.empty())
    {
        int nod = h.top().second.second ;
        if (t[nod] == 0)
        {
                t[nod] = h.top().second.first;
                Cost += h.top().first;


                cnt ++ ;
                sol[cnt].st = h.top().second.first ;
                sol[cnt].dr = h.top().second.second ;

                h.pop() ;

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


        }
        else h.pop();
    }


}
int main()
{

    f >> N >> M ;
    for (int i = 1 ; i <= M ; ++i)
    {
        f >> x >> y >> cost;
        v[x].push_back(make_pair(cost,y)) ;
        v[y].push_back(make_pair(cost,x)) ;
    }
    Solve ();


    g << Cost << '\n' ;
    g << cnt - 1<< '\n';
    for (int i = 2; i <= cnt ; ++i)
        g << sol[i].dr << ' ' << sol[i].st << '\n';

    f.close() ;
    g.close() ;
    return 0;

}