#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
struct chestie{
    int from,to,cost;
};
struct comp{
   bool operator()(const chestie& l, const chestie& r){
       return (l.cost > r.cost);
   }
 };
int N,M, viz[200200];
long long ans;
queue <int> q;
vector <pair<int,int> > sol, L[200200];
priority_queue <chestie, vector<chestie>, comp> pq;

inline void scan();
inline void prim();
inline void print();
int main()
{
    scan();

    prim();

    print();

    return 0;
}

inline void scan()
{
    int x,y,cost;
    cin>>N>>M;
    for(int i=1; i<=M; ++i)
    {
        cin>>x>>y>>cost;
        L[x].push_back({y,cost});
        L[y].push_back({x,cost});
    }
}
inline void print()
{
    cout<<ans<<'\n';
    cout<<sol.size()<<'\n';
    for(int i=0; i<sol.size(); ++i)
        cout<<sol[i].first<<' '<<sol[i].second<<'\n';
}
inline void prim()
{
    int nxt,nod,nr;
    q.push(1);
    viz[1]=1; nr=1;
    while(!q.empty() && nr<N)
    {
        nr++;
        nod=q.front(); q.pop();

        for(auto nn: L[nod])
            if(!viz[nn.first])
                pq.push({nod,nn.first,nn.second});


        nxt=pq.top().to;
        while(!pq.empty() && viz[nxt])
        {
            pq.pop();
            nxt=pq.top().to;
        }

        if(!viz[nxt])
        {
            viz[nxt]=1;
            ans+=pq.top().cost;
            q.push(nxt);
            sol.push_back({pq.top().from,pq.top().to});
        }
    }
}