#include <bits/stdc++.h>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

const int N=200005;
int n,m,cost,vis[N];
vector <pair <int,int> > v[N],apm;
priority_queue <tuple <int,int,int >> pq;

void adauga(int nod)
{
    vis[nod]=1;
    for(auto it: v[nod])
    {
        int vec,cst;
        tie(vec,cst)=it;
        if(!vis[vec])
            pq.push(make_tuple(-cst,nod,vec));
    }
}


int main()
{
    f>>n>>m;
    for(;m;m--)
    {
        int x,y,c;
        f>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
        v[y].push_back(make_pair(x,c));

    }
    adauga(1);
    while(pq.size())
    {
        int x,y,c;
        tie(c,x,y)=pq.top();
        pq.pop();
        if(vis[x])
            swap(x,y);
        if(!vis[x])
        {
            cost-=c;
            apm.push_back(make_pair(x,y));
            adauga(x);
        }
    }
    g<<cost<<'\n'<<n-1<<'\n';
    for(auto it: apm)
        g<<it.first<<' '<<it.second<<'\n';
    return 0;
}