#include <bits/stdc++.h>
#define secv pair <int, pair<int , int> >
#define NMAX 200010
#define pb push_back
using namespace std;
ifstream f ("apm.in") ;
ofstream g ("apm.out") ;
int N , M , T[NMAX] ,x , y , c , cnt = 0, Cost = 0 ;
vector <pair <int , int > > v[NMAX] ;
vector <pair <int,int> > sol;
priority_queue <secv , vector <secv> , greater <secv> > h;
void Prim()
{
    h.push({0,{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;

            sol.pb({h.top().second.first,h.top().second.second}) ; // constr solutia

            h.pop();
            for (int i = 0 ; i < v[nod].size() ; ++i)
            {
                int vec = v[nod][i].second;
                if (T[vec] == 0) h.push({v[nod][i].first , {nod , vec}});
            }
        }
        else h.pop();
    }
}
int main()
{
    f >> N >> M ;
    for (int i = 1 ;  i <= M ; ++i)
    {
        f >> x >> y >> c;
        v[x].pb({c,y}) ;
        v[y].pb({c,x});
    }
    Prim();
    g << Cost << '\n' ;
    g << sol.size() - 1<< '\n';
    for (int i = 1; i < sol.size() ; ++i) g << sol[i].first << ' ' << sol[i].second << '\n' ;
    f.close();
    g.close();
    return 0 ;
}