#include <fstream>
#include <queue>
#include <climits>
#include <vector>
#define w 200002
using namespace std;
struct cost{int v,c,t;};
vector <cost> a[w];
int ct;
vector <cost> muc;
class prei
{
    public:
    bool operator()(const cost &p1, const cost &p2)
    {
        return p1.c>p2.c;
    }
};
priority_queue <cost, vector <cost>, prei> q;
bool viz[w];
void solve()
{
    cost x,y;
    int i;
    while (!q.empty())
    {
        x=q.top();q.pop();
        if ((!viz[x.v]))
        {
            for (i=0;i<a[x.v].size();i++)
            {
                y=a[x.v][i];y.t=x.v;
                if(!viz[y.v]) q.push(y);
            }
            viz[x.v]=1;ct+=x.c;muc.push_back({x.t,x.v,0});
        }
    }
}
int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    int n,i,m,x,y,c;
    f>>n>>m;
    for (i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        a[x].push_back({y,c,0});
        a[y].push_back({x,c,0});
    }
    q.push({1,0,0});
    solve();
    g<<ct<<'\n'<<muc.size()-1<<'\n';
    for (i=1;i<muc.size();i++)
    {
        g<<muc[i].v<<' '<<muc[i].c<<'\n';
    }
    f.close();
    g.close();
    return 0;
}